hdu2391_ Filthy_Rich(简单dp)

本文主要是介绍hdu2391_ Filthy_Rich(简单dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

此题的题意就是给一个图，从图的左上角走到图的右下角，只能向右,向下或者右下走。轨迹上的数字求和，并找出最大值。
1
3 4
1 10 8 8
0 0 1 8
0 27 0 4
从数据分析，此题若使用普通的贪心算法，并不能解除正确的结果。因为在一个位置有三种走法，如果仅仅选择三种走法中的最大值。那么后面的路径也会受到这一步的影响可能有更大的值不能走到。所以简单的贪心算法并不能解决这个问题。而且这段时间我主要做的是贪心的专项。对dp早已有些生疏。所以看了一个题解。下面是我的代码！题目的核心就是使用一个dp二维数组来保存对应的每个位置的最大值。对于 i j位置来说它的值有可能有三个方向求来。一是上面的数字加map[i][j] ,也有可能是左边的数字，也有可能是左上角的数字。所以对于dp[i][j]来说它应该是以上三个方向dp的最大值加上map[i][j]才能求得当前的dp的值。在下的代码如下:

#include<iostream>
#include<algorithm>
using namespace std;#define MAXN 1002int map[MAXN][MAXN],dp[MAXN][MAXN];int find_max(int x,int y)
{int w=0,u=0,w_u=0;if(y-1>=0)w=dp[x][y-1];if(x-1>=0)u=dp[x-1][y];if(x-1>=0&&y-1>=0)w_u = dp[x-1][y-1];w = w>u?w:u;return w>w_u?w:w_u;      
}
int main()
{int T;scanf("%d",&T);int TC=1;for(;TC<=T;TC++){int r,c;scanf("%d%d",&r,&c);for(int i=0;i<r;i++)for(int j=0;j<c;j++)  scanf("%d",&map[i][j]);   int max;for(int i=0;i<r;i++)for(int j=0;j<c;j++)dp[i][j]=find_max(i,j)+map[i][j];printf("Scenario #%d:\n%d\n\n",TC,dp[r-1][c-1]);}return 0;    
}