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; }