欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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 }

结果:

dp算法之平安果路径问题c++

输入:

2 4

1 2 3 40

6 7 8 90

输出:

1 2 3 40 90

136