dp算法之平安果路径问题c++
程序员文章站
2022-04-14 20:29:23
前文:https://www.cnblogs.com/ljy1227476113/p/9563101.html 在此基础上更新了可以看到行走路径的代码。 代码: 结果: 输入: 2 4 1 2 3 40 6 7 8 90 输出: 1 2 3 40 90 136 ......
前文:
在此基础上更新了可以看到行走路径的代码。
代码:
1 #include <iostream> 2 using namespace std; 3 int ivec[10001][10001]; 4 int dp[10001][10001]; 5 int que[10001]; 6 int main() 7 { 8 int m, n; 9 int i, j; 10 int tail = 1; 11 while (cin >> m >> n) 12 { 13 que[10001] = { 0 }; 14 for (i = 1; i <= m; i++) 15 { 16 for (j = 1; j <= n; j++) 17 { 18 cin >> ivec[i][j]; 19 } 20 } 21 que[0] = ivec[m][n]; 22 dp[1][1] = ivec[1][1]; 23 for (i = 2; i <= m; i++) 24 { 25 dp[i][1] = dp[i - 1][1]+ivec[i][1]; 26 } 27 for (j = 2; j <= n; j++) 28 { 29 dp[1][j] = dp[1][j - 1]+ivec[1][j]; 30 } 31 for (i = 2; i <= m; i++) 32 { 33 for (j = 2; j <= n; j++) 34 { 35 dp[i][j] = ((dp[i - 1][j] < dp[i][j - 1]) ? dp[i][j - 1] : dp[i - 1][j]) + ivec[i][j]; 36 } 37 } 38 i = m, j = n; 39 while(tail <= m + n - 2) 40 { 41 if (dp[i - 1][j] >= dp[i][j - 1]) 42 { 43 que[tail++] = ivec[i - 1][j]; 44 i--; 45 } 46 else 47 { 48 que[tail++] = ivec[i][j - 1]; 49 j--; 50 } 51 } 52 for (i = 1; i <= m; i++) 53 { 54 for (j = 1; j <= n; j++) 55 cout << dp[i][j] << " "; 56 cout << endl; 57 } 58 for (i = m + n - 2; i >= 0; i--) 59 cout << que[i] << " "; 60 cout << endl; 61 cout << dp[m][n] << endl; 62 } 63 return 0; 64 }
结果:
输入:
2 4
1 2 3 40
6 7 8 90
输出:
1 2 3 40 90
136
上一篇: 微信小程序上传图片