AOJ 2272 - Cicada

5分かかった．北，西に移動しないので{ある地点までの最小の虫} = min({その西までの最小の虫}, {その北までの最小の虫}) + {その地点にいる虫の数}で求まります．
あとは再帰的に計算するだけです．

#include<iostream>

int memo[50][50];

int main(){
	int H, W, map[50][50];
	std::cin >> H >> W;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			char c;
			std::cin >> c;
			map[i][j] = c - '0';
		}
	}

	for(int i=1;i<H;i++)memo[i][0] = memo[i-1][0] + map[i][0];
	for(int j=1;j<W;j++)memo[0][j] = memo[0][j-1] + map[0][j];
	for(int i=1;i<H;i++){
		for(int j=1;j<W;j++){
			memo[i][j] = std::min(memo[i-1][j] + map[i][j], memo[i][j-1] + map[i][j]);
		}
	}

	std::cout << memo[H-1][W-1] << std::endl;
}