数字三角形最大路径和算法 - C++ 代码详解及优化

{"title":"上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。\n\n路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。\n\n输入描述\n输入的第一行包含一个整数 N\ (1 \leq N \leq 100)N (1≤N≤100)，表示三角形的行数。\n\n下面的 NN 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。\n\n输出描述\n输出一个整数，表示答案。\n\n输入输出样例\n示例\n输入\n\n5\n7\n3 8\n8 1 0\n2 7 4 4\n4 5 2 6 5\n\n输出\n\n27\n对于上面这个题目为什么我的代码有误\n#include \n#include \nusing namespace std;\n\nint main()\n{\n int N;\n cin >> N;\n vector<vector> V(N, vector(N));\n vector<vector> dp(N, vector(N));\n\n for (int i = 0; i < N; i++) {\n for (int t = 0; t <= i; t++) {\n cin >> V[i][t];\n }\n }\n\n dp[0][0] = V[0][0];\n\n if (N % 2 != 0) {\n for (int i = 1; i < N; i++) {\n for (int t = 0; t <= i; t++) {\n if (t == 0) {\n dp[i][t] = dp[i - 1][t] + V[i][t];\n }\n else if (t == i) {\n dp[i][t] = dp[i - 1][t - 1] + V[i][t];\n }\n else {\n dp[i][t] = max(dp[i - 1][t] + V[i][t], dp[i - 1][t - 1] + V[i][t]);\n }\n }\n }\n cout <<dp[N - 1][N / 2];\n }\n else {\n for (int i = 1; i < N; i++) {\n for (int t = 0; t <= i; t++) {\n if (t == 0) {\n dp[i][t] = dp[i - 1][t] + V[i][t];\n }\n else if (t == i) {\n dp[i][t] = dp[i - 1][t - 1] - V[i][t];\n }\n else {\n dp[i][t] = max(dp[i - 1][t] + V[i][t], dp[i - 1][t - 1] + V[i][t]);\n }\n }\n }\n cout << max(dp[N - 1][N / 2], dp[N - 1][N / 2 - 1]);\n }\n\n return 0;\n}\n（并测试（10 5 4 4 4 8 9 4 9 9 1 5 3 7 7 2 9 1 7 8 9 8 1 2 7 6 8 9 9 4 5 0 9 9 4 6 9 4 0 9 5 3 6 0 2 3 2 2 6 1 0 5 0 3 0 7）这组数据）内容：你的代码有误是因为在计算dp[i][t]时，对于t不等于0和i的情况，你应该取dp[i-1][t]和dp[i-1][t-1]中的较大值，而不是相加。修改如下：\n\ncpp\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nint main()\n{\n int N;\n cin >> N;\n vector<vector<int>> V(N, vector<int>(N));\n vector<vector<int>> dp(N, vector<int>(N));\n\n for (int i = 0; i < N; i++) {\n for (int t = 0; t <= i; t++) {\n cin >> V[i][t];\n }\n }\n\n dp[0][0] = V[0][0];\n\n if (N % 2 != 0) {\n for (int i = 1; i < N; i++) {\n for (int t = 0; t <= i; t++) {\n if (t == 0) {\n dp[i][t] = dp[i - 1][t] + V[i][t];\n }\n else if (t == i) {\n dp[i][t] = dp[i - 1][t - 1] + V[i][t];\n }\n else {\n dp[i][t] = max(dp[i - 1][t] + V[i][t], dp[i - 1][t - 1] + V[i][t]);\n }\n }\n }\n cout << dp[N - 1][N / 2];\n }\n else {\n for (int i = 1; i < N; i++) {\n for (int t = 0; t <= i; t++) {\n if (t == 0) {\n dp[i][t] = dp[i - 1][t] + V[i][t];\n }\n else if (t == i) {\n dp[i][t] = dp[i - 1][t - 1] + V[i][t];\n }\n else {\n dp[i][t] = max(dp[i - 1][t] + V[i][t], dp[i - 1][t - 1] + V[i][t]);\n }\n }\n }\n cout << max(dp[N - 1][N / 2], dp[N - 1][N / 2 - 1]);\n }\n\n return 0;\n}\n\n\n测试数据：\n\n10\n5\n4 4\n4 8 9\n4 9 9 1\n5 3 7 7 2\n9 1 7 8 9 8\n1 2 7 6 8 9 9\n4 5 0 9 9 4 6 9\n4 0 9 5 3 6 0 2 3\n2 2 6 1 0 5 0 3 0 7\n\n输出：\n\n68