c++中如何实现动态规划最小路径和_c++动态规划最小路径和方法

#include <iostream><br>#include <vector><br>#include <algorithm><br>using namespace std;<br><br>int minPathSum(vector<vector<int>>& grid) {<br>    if (grid.empty() || grid[0].empty()) return 0;<br>    int m = grid.size();<br>    int n = grid[0].size();<br><br>    // 创建 dp 表，可以用原数组优化空间<br>    vector<vector<int>> dp(m, vector<int>(n));<br>    dp[0][0] = grid[0][0];<br><br>    // 初始化第一行<br>    for (int j = 1; j < n; ++j) {<br>        dp[0][j] = dp[0][j-1] + grid[0][j];<br>    }<br><br>    // 初始化第一列<br>    for (int i = 1; i < m; ++i) {<br>        dp[i][0] = dp[i-1][0] + grid[i][0];<br>    }<br><br>    // 填充其余状态<br>    for (int i = 1; i < m; ++i) {<br>        for (int j = 1; j < n; ++j) {<br>            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);<br>        }<br>    }<br><br>    return dp[m-1][n-1];<br>}<br><br>// 测试示例<br>int main() {<br>    vector<vector<int>> grid = {<br>        {1, 3, 1},<br>        {1, 5, 1},<br>        {4, 2, 1}<br>    };<br>    cout << "最小路径和: " << minPathSum(grid) << endl; // 输出 7<br>    return 0;<br>}

int minPathSum(vector<vector<int>>& grid) {<br>    int m = grid.size(), n = grid[0].size();<br>    vector<int> dp(n);<br>    dp[0] = grid[0][0];<br>    <br>    // 初始化第一行<br>    for (int j = 1; j < n; ++j) {<br>        dp[j] = dp[j-1] + grid[0][j];<br>    }<br>    <br>    for (int i = 1; i < m; ++i) {<br>        dp[0] += grid[i][0]; // 更新每行第一个元素<br>        for (int j = 1; j < n; ++j) {<br>            dp[j] = grid[i][j] + min(dp[j], dp[j-1]);<br>        }<br>    }<br>    <br>    return dp[n-1];<br>}