宝贝，生日快乐！！！LevOJ P1236 夺取宝藏

思路：

对于任意一点（i，j）来说，只能从（i-1，j）或者（i，j-1）到达（i，j）。

设 dp[i] [j] 表示到达点（i，j）所能获取的最大价值，则有

​ $dp[i][j]=max(dp[i-1][j],dp[i][j-1])+num[i][j]$

遍历所有点，最后 dp[m] [n] 就是所能获得的最大价值。

时间复杂度 O(m*n) 。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int m,n;
int num[1005][1005];
int dp[1005][1005];

int main(){
    while(scanf("%d%d",&m,&n)!=EOF){
        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                cin>>num[i][j];
            }
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+num[i][j];
            }
        }
        cout<<dp[m][n]<<endl;
    }
    return 0;
}