POJ 2704 Pascal's Travels

問題
http://poj.org/problem?id=2704

解法
ゴールから逆にたどるように考えるといい。

ゴールの方から道をみると下のような漸化式が成り立つ。

a[i][j] := そのマスに書いてある数字
dp[i][j] := そこの場所からゴールまで行き方の総数

dp[N-1][N-1] = 1
dp[i][j] = dp[ i+a[i][j] ][j] + dp[i][ j+a[i][j] ]

この漸化式を用いて、動的計画法を使えばO(N^2)で計算できる

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;
const int MAX_N = 34;
int a[MAX_N][MAX_N];
ll dp[MAX_N][MAX_N];
int N;
int main(){
	while(~scanf("%d",&N) && N!=-1){
		for(int i = 0; i < N; i++){
			char c;
			scanf("%c", &c);
			for(int j = 0; j < N; j++){
				char t;
				scanf("%c", &t);
				a[i][j] = t - '0';
				dp[i][j] = 0;
			}
		}
		dp[N-1][N-1] = 1;
		for(int i=N-1;i>=0;i--){
			for(int j=N-1;j>=0;j--){
				if(i==N-1 && j==N-1) continue;
				if(a[i][j]+j < N)
					dp[i][j] += dp[i][j+a[i][j]];
				if(a[i][j]+i < N)
					dp[i][j] += dp[i+a[i][j]][j];
			}
		}
		printf("%lld\n", dp[0][0]);
	}
	return 0;
}