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

前文：

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

代码：

 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