采花生果：动态规划解题思路及C++实现

"采花生果" 题目描述 \n 在参加"采花生这个项目比赛时，考官会出示一块n行、m列的花生田，一共种了n"m株花生苗，每株花生植株下都结了一定数量的花生果，选手一开\n始站在第1行，第1列的位置，要求用最短的时间找到结花生果最多的一株花生植株（数据保证花生果最多的植株只有一株），然后按先向南（下）\n走，再向东（右）的路线顺序去采摘它的花生果，沿路经过的其他花生植株下面的花生果也要一并摘下来，但不允许采摘没有路过的花生植株，否则\n依犯规出局处理。问这个选手一共可以采摘多少粒花生果？\n \n 输入：\n 第1行：两个整数nm(1<n,m<=100),表示花生田一共有n行m列\n 第2.n+1行：每行m个空格隔开的整数，第i+1行的第]个整数Pij(0<=Pij<=700)表示花生田里植株()下花生的数目，0表示该植株下没有花生。\n 输出：\n 一行，一个整数，表示选手一共摘到的花生果数目。\n \n 样例输入：\n 5 6\n 5 7 4 5 1 13\n 9 6 3 2 8 7\n 10 14 0 1 9 4\n 4 6 9 18 25 0\n 3 1 2 9 0 2\n \n 样例输出：\n 86\n \n 要求：\n 时间限制：1.0Sec\n 内存限制：128MB\n \n 用C++，尽量降低时间复杂度，确保答案正确\n \n 内容：一种可行的解题思路是使用动态规划。我们可以定义一个二维数组dp，其中dp[i][j]表示从第1行1列位置开始，到达第i行第j列位置时能够采摘到的花生果数目的最大值。\n \n 首先，我们可以初始化dp的第一行和第一列，因为从起始位置到达这些位置时，只能采摘到当前位置的花生果。\n \n 然后，我们从第二行第二列开始，对于每个位置(i, j)，我们可以选择从上方位置(i-1, j)或者左侧位置(i, j-1)中的较大值，再加上当前位置的花生果数目Pij，更新dp[i][j]的值。\n \n 最后，dp的最后一个元素dp[n][m]即为选手能够采摘到的最大花生果数目。\n \n 具体实现如下：\n \n cpp\n #include <iostream>\n #include <vector>\n using namespace std;\n \n int main() {\n int n, m;\n cin >> n >> m;\n vector<vector<int>> peanuts(n, vector<int>(m));\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n cin >> peanuts[i][j];\n }\n }\n \n vector<vector<int>> dp(n, vector<int>(m));\n dp[0][0] = peanuts[0][0];\n // 初始化第一行\n for (int j = 1; j < m; j++) {\n dp[0][j] = dp[0][j-1] + peanuts[0][j];\n }\n // 初始化第一列\n for (int i = 1; i < n; i++) {\n dp[i][0] = dp[i-1][0] + peanuts[i][0];\n }\n \n // 动态规划转移方程\n for (int i = 1; i < n; i++) {\n for (int j = 1; j < m; j++) {\n dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + peanuts[i][j];\n }\n }\n \n cout << dp[n-1][m-1] << endl;\n \n return 0;\n }\n \n \n 该算法的时间复杂度为O(nm)，在给定的数据规模下是可以接受的。