题目:平安果

题目介绍:给出一个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 = ; i < m; ++i)
{
for (j = ; j < n; ++j)
{
cin >> ivec[i][j];
}
}
vector<vector<int>> dp(ivec);
for (i = ; i < m; ++i)
{
dp[i][] += dp[i - ][];
}
for (j = ; j < n; ++j)
{
dp[][j] += dp[][j - ];
}
for (i = ; i < m; ++i)
{
for (j = ; j < n; ++j)
{
dp[i][j] += (dp[i - ][j] < dp[i][j - ]) ? dp[i][j - ] : dp[i - ][j];
}
}
cout << dp[m - ][n - ] << endl;
}
return ;
}

结果如下图所示:

华为笔试——C++平安果dp算法-LMLPHP

05-04 00:31