动态规划____有重叠子问题的搜索,都可以转为记忆化搜索

1.细节还是挺重要的,m n一定别写错

2.用INF标记未访问的点的方法 确实不错

3.如题:有重叠子问题的搜索,都可以转为记忆化搜索

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define INF 0
#define MAX 110

using namespace std;

int input[MAX][MAX];
int dp[MAX][MAX];
int m, n;

int max(int a, int b)
{
    return a>b?a:b;
}

int d(int i , int j)
{
    if(dp[i][j] != INF)
        return dp[i][j];
    else
    {
        dp[i][j] = 1;//注意此处的赋值 每一道题都有各自的含义与赋值
        
        if(i-1 >= 0 && input[i-1][j] < input[i][j]) dp[i][j] = max(d(i-1,j) + 1, dp[i][j]);
        if(j-1 >= 0 && input[i][j-1] < input[i][j]) dp[i][j] = max(d(i,j-1) + 1, dp[i][j]);
        if(i+1 < m  && input[i+1][j] < input[i][j]) dp[i][j] = max(d(i+1,j) + 1, dp[i][j]);
        if(j+1 < n  && input[i][j+1] < input[i][j]) dp[i][j] = max(d(i,j+1) + 1, dp[i][j]);

        return dp[i][j];
    }
}

int main()
{
    int i, j;
    int N;

    scanf("%d", &N);
    while(N--)
    {

            memset(dp, INF, sizeof(dp));
            scanf("%d%d", &m, &n);

            for(i = 0; i < m; i++)
            {
                for(j = 0; j < n; j++)
                {
                    scanf("%d", &input[i][j]);
                }
            }

            int max = 0;
            for(i = 0; i < m; i++)
            {
                for(j = 0; j < n; j++)
                {
                    int temp = d(i, j);
                    if(temp > max)
                        max = temp;
                }
            }    
            printf("%d
", max);


    }
    return 0;
}

http://poj.org/problem?id=1088 滑雪