hdu1208 Pascal's Travels

求从（0, 0 )  到 ( n - 1, n - 1 ) 有几种不同的方式。。。

dp[i][j]表示到i， j位置处有几种方式

tmp = data[i][j];

dp[i + tmp][j] += dp[i][j]

dp[i][j + tmp] += dp[i][j]

#include <stdio.h>

#include <string.h>

#include <iostream>

using namespace std;

int ct, tmp, data[40][40];

__int64 dp[40][40];

int main ( ) {

while ( scanf ( "%d", &ct ) && ct + 1 ) {

for ( int i = 0; i < ct; ++i )

for ( int j = 0; j < ct; ++j )

scanf ( "%1d", &data[i][j] );

memset ( dp, 0, sizeof ( dp ) );

dp[0][0] = 1;

for ( int i = 0; i < ct; ++i )

for ( int j = 0; j < ct; ++j ) {

if ( data[i][j] == 0 ) continue;

dp[i + data[i][j]][j] += dp[i][j];

dp[i][j + data[i][j]] += dp[i][j];

}

printf ( "%I64dn", dp[ct - 1][ct - 1] );

}

}