矩阵动态规划-最小路径和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-01-02 11:00:20
 * 最后修改: 2025-01-02 11:24:06
 * 文件描述: 最小路径和
****************************************************************/
#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

// 打印路径的函数
void printPath(vector<vector<int>>& grid) {
    int m = grid.size() - 1;
    int n = grid[0].size() - 1;
    vector<pair<int, int>> result;

    while (m > 0 || n > 0) {
        result.push_back({m, n});
      if (m == 0) {
            // 在第一行，只能向左移动
            --n;
        } else if (n == 0) {
            // 在第一列，只能向上移动
            --m;
        } else {
            // 比较上方和左侧的路径和，选择较小的方向
            if (grid[m - 1][n] < grid[m][n - 1]) {
                --m;
            } else {
                --n;
            }
        }
    }
    result.push_back({0, 0});

    reverse(result.begin(), result.end());
    cout << "路径为: ";
    for (const auto& p : result) {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    cout << endl;
}

// 主函数
int minPathSum(vector<vector<int>>& grid) {
    // 获取矩阵的行数和列数
    int m = grid.size();
    int n = grid[0].size();

    // 初始化第一行
    for (int j = 1; j < n; ++j) {
        grid[0][j] += grid[0][j - 1];
    }

    // 初始化第一列
    for (int i = 1; i < m; ++i) {
        grid[i][0] += grid[i - 1][0];
    }

    // 动态规划：更新其他位置的最小路径和
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            // 其他位置，可以从左侧或上方到达，取路径和较小的
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
        }
    }

    // 返回终点位置的最小路径和
    return grid[m - 1][n - 1];
}

int main() {
    // 示例输入
    vector<vector<int>> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };

    vector<vector<int>> originalGrid = grid; // 保存原始网格用于路径追踪

    // 调用函数并输出结果
    cout << "最小路径和: " << minPathSum(grid) << endl;

    // 打印路径
    printPath(grid);

    return 0;
}