HDU 1208 Pascal's Travels

暑假集训的时候做过了，当时大神XX不到30分钟搞定了，我陷入了深搜的陷阱中了。

题意：从[1,1]出发到[n,n]，每次到达的格子都要按照格子里的数字走。问可以走到终点的数量是多少。

1.明显的递推。每个可能走到的格子都是由上个格子转移来的，那么能到达上一个格子的步数肯定成为到达该格子的数量一部分。

2.那么将每个格子可能去到的下一个格子都递推下去。只能向下向右走。

3.递推的方法，或者记忆化搜索。

#include <stdio.h>
#include <iostream>
using namespace std;

__int64 path[40][40];
int maz[40][40] , n;

void dp()
{
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            path[i][j] = 0;
        }
    }
    path[1][1] = 1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==n && j==n) break;
            int t = maz[i][j];
            if(path[i][j] > 0)
            {
                if(t + i <= n)
                {
                    path[t+i][j] += path[i][j];
                }
                if(t + j <= n)
                {
                    path[i][j+t] += path[i][j];
                }
            }
        }
    }
}
#include <string.h>
int main()
{
    char st[100];
    while(scanf("%d",&n) , n >= 0)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%s",st);
            for(int j=0;j<strlen(st);j++)
            {
                maz[i][j+1] = st[j] - '0';
            }
        }
        dp();
        printf("%I64d
",path[n][n]);
    }
    return 0;
}