c++ - 使用动态规划打印矩阵中所有可能路径中总和最小的路径

Question

我想打印允许您向右或向下移动的矩阵的最小总和。我能够获得成本，但我不确定如何打印所有可能路径中总和最小的路径。

#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;

    #define M 3
    #define N 3

    int findMinCost(int cost[M][N])
    {
        int T[M][N];

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                T[i][j] = cost[i][j];

                if (i == 0 && j > 0)
                    T[0][j] += T[0][j - 1];

                else if (j == 0 && i > 0)
                    T[i][0] += T[i - 1][0];

                else if (i > 0 && j > 0)
                    T[i][j] += min(T[i - 1][j], T[i][j - 1]);

            }
        }

        return T[M - 1][N - 1];
    }

    int main()
    {
        int cost[M][N] =
        {
            { 9,-2,10 },
            { 15,23,-10 },
            { 40,16,2 },
        };

        cout << "The minimum cost is " << findMinCost(cost);

        return 0;
    }

Answer 1

您可以使用另一个二维数组 std::pair存储达到最优解的路径索引。

重构解决方案

1. 为了重构解决方案，声明path存储为达到最佳解决方案所采用的最后路径。

std::pair<int,int> path[M][N]

1. 在你的内部循环中，每次 T[i][j]被计算，也计算path[i][j]

   if (i == 0 && j > 0) {
     T[0][j] += T[0][j - 1];
     path[0][j] = std::make_pair(0, j - 1);
   }
   else if (j == 0 && i > 0) {
     T[i][0] += T[i - 1][0];
     path[i][0] = std::make_pair(i - 1, 0);
   }
   else if (i > 0 && j > 0) {
     if (T[i - 1][j] < T[i][j - 1]) {
       T[i][j] += T[i - 1][j];
       path[i][j] = std::make_pair(i - 1, j);
     } else {
       T[i][j] += T[i][j - 1];
       path[i][j] = std::make_pair(i, j - 1);
     }
   }
   

2. 最后，使用 path array 使用递归函数重构解如下(也可以转化为迭代解)

   void printPath(int i, int j, std::pair<int,int> path[M][N], int cost[M][N])
   {
     if (!i && !j) {
       cout << cost[i][j] << ' ';
       return;
     }
     printPath(path[i][j].first, path[i][j].second, path, cost);
     cout << cost[i][j] << ' ';
   }
   

演示:here