数字三角形最大路径和问题：代码优化与测试数据修正

{/u0022title/u0022: /u0022数字三角形最大路径和问题：代码优化与测试数据修正/u0022, /u0022description/u0022: /u0022本文介绍了数字三角形最大路径和问题的算法实现，并对代码进行了优化，修正了测试数据中的错误。同时还提供了详细的代码分析和测试用例。/u0022, /u0022keywords/u0022: /u0022数字三角形, 最大路径和, 动态规划, 代码优化, 测试数据/u0022, /u0022content/u0022: /u0022问题出在第二个else语句的计算中。在偶数行的情况下，左下走的次数与右下走的次数相差不能超过1，因此在计算dp[i][t]时，需要比较dp[i-1][t]和dp[i-1][t+1]两个值，而不是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//n//n10 //n5 4 //n4 4 4 //n8 9 4 9 //n9 1 5 3 7 //n7 2 9 1 7 8 //n9 8 1 2 7 6 8 //n9 9 4 5 0 9 9 4 //n6 9 4 0 9 5 3 6 0 //n2 3 2 2 6 1 0 5 0 3 //n0 7 //n//n//n经过修改后的代码可以输出正确的结果。/u002