题目：平安果
 
题目介绍：ASP站长网给出一个m*n的格子，每个格子里有一定数量的平安果，现在要求从左上角顶点（1,1）出发，每次走一格并拿走那一格的所有平安果，且只能向下或向右前进，最终到达右下角顶点（m，n），要求求出能拿走的平安果的最大数值。
 
输入：第一行有两个数值m，n，然后是m行n列数值。
 
输出：一个数值代表平安果的最大数量。
 
例：
 
输入：
 
4 4
 
1 2 4 8
 
10 14 3 9
 
17 6 7 20
 
12 5 21 23
 
输出：
 
89
 
分析：这是一种比较典型的dp算法（动态规划）的题目，每一格获取的平安果最大数值都与上格或左格有关（即交叠问题），且无后效性。这题也证明了动态规划可以解决贪心算法所解决不了的问题，若用贪心算法，不一定能得出总体最优解。
 
状态方程：dp[ i ][ j ]=max{ dp[ i-1 ][ j ] , dp[ i ][ j-1 ]}+A[ i ][ j ]
 
代码如下：
 
#include <vector>
#include <iostream>
using namespace std;
int main()
{
    int m, n;
    int i, j;
    while (cin >> m >> n)
    {
        vector<vector<int>> ivec(m, vector<int>(n));
        for (i = 0; i < m; ++i)
        {
            for (j = 0; j < n; ++j)
            {
                cin >> ivec[i][j];
            }
        }
        vector<vector<int>> dp(ivec);
        for (i = 1; i < m; ++i)
        {
            dp[i][0] += dp[i – 1][0];
        }
        for (j = 1; j < n; ++j)
        {
            dp[0][j] += dp[0][j – 1];
        }
        for (i = 1; i < m; ++i)
        {
            for (j = 1; j < n; ++j)
            {
                dp[i][j] += (dp[i – 1][j] < dp[i][j – 1]) ? dp[i][j – 1] : dp[i – 1][j];
            }
        }
        cout << dp[m – 1][n – 1] << endl;
    }
    return 0;
}