最大礼物价值 【二维dp 记忆化搜索】 特别水
在一个mXn的棋盘的每一个格子都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格。直到到达棋盘的右下角。
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
给定一个前以及其上面的礼物，请计算你最多能拿到多少价值的礼物。
不喜欢递归……师兄问起来，墨迹了一个多小时才写出来……菜的一逼 鄙视自己orz
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int num[300][300];
int dp[300][300];
int cal(int x,int y)
{
if(x==n+1||y==m+1) return 0;
if(dp[x][y]!=0) return dp[x][y];
return dp[x][y]=num[x][y]+max(cal(x+1,y),cal(x,y+1));
}
int main()
{
freopen("cin.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&num[i][j]);
printf("%d
",cal(1,1));
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%d ",dp[i][j]);
printf("
");
}
return 0;
}
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出145
