经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
dp算法之平安果路径问题c++
来源:cnblogs  作者:会武术之白猫  时间:2018/10/31 9:05:26  对本文有异议

前文:https://www.cnblogs.com/ljy1227476113/p/9563101.html

在此基础上更新了可以看到行走路径的代码。

代码:

  1. 1 #include <iostream>
  2. 2 using namespace std;
  3. 3 int ivec[10001][10001];
  4. 4 int dp[10001][10001];
  5. 5 int que[10001];
  6. 6 int main()
  7. 7 {
  8. 8 int m, n;
  9. 9 int i, j;
  10. 10 int tail = 1;
  11. 11 while (cin >> m >> n)
  12. 12 {
  13. 13 que[10001] = { 0 };
  14. 14 for (i = 1; i <= m; i++)
  15. 15 {
  16. 16 for (j = 1; j <= n; j++)
  17. 17 {
  18. 18 cin >> ivec[i][j];
  19. 19 }
  20. 20 }
  21. 21 que[0] = ivec[m][n];
  22. 22 dp[1][1] = ivec[1][1];
  23. 23 for (i = 2; i <= m; i++)
  24. 24 {
  25. 25 dp[i][1] = dp[i - 1][1]+ivec[i][1];
  26. 26 }
  27. 27 for (j = 2; j <= n; j++)
  28. 28 {
  29. 29 dp[1][j] = dp[1][j - 1]+ivec[1][j];
  30. 30 }
  31. 31 for (i = 2; i <= m; i++)
  32. 32 {
  33. 33 for (j = 2; j <= n; j++)
  34. 34 {
  35. 35 dp[i][j] = ((dp[i - 1][j] < dp[i][j - 1]) ? dp[i][j - 1] : dp[i - 1][j]) + ivec[i][j];
  36. 36 }
  37. 37 }
  38. 38 i = m, j = n;
  39. 39 while(tail <= m + n - 2)
  40. 40 {
  41. 41 if (dp[i - 1][j] >= dp[i][j - 1])
  42. 42 {
  43. 43 que[tail++] = ivec[i - 1][j];
  44. 44 i--;
  45. 45 }
  46. 46 else
  47. 47 {
  48. 48 que[tail++] = ivec[i][j - 1];
  49. 49 j--;
  50. 50 }
  51. 51 }
  52. 52 for (i = 1; i <= m; i++)
  53. 53 {
  54. 54 for (j = 1; j <= n; j++)
  55. 55 cout << dp[i][j] << " ";
  56. 56 cout << endl;
  57. 57 }
  58. 58 for (i = m + n - 2; i >= 0; i--)
  59. 59 cout << que[i] << " ";
  60. 60 cout << endl;
  61. 61 cout << dp[m][n] << endl;
  62. 62 }
  63. 63 return 0;
  64. 64 }

结果:

输入:

2 4

1 2 3 40

6 7 8 90

输出:

1 2 3 40 90

136

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号