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

最小路径和可通过动态规划求解，定义dpi为从(0,0)到(i,j)的最小路径和，状态转移方程根据边界条件分三种情况，初始化第一行和第一列后，递推填充其余位置，最终结果为dpm-1；空间优化版本使用一维数组将空间复杂度降为O(n)，按行更新dp值，核心逻辑不变。

在C++中实现动态规划求解“最小路径和”问题，通常针对一个二维网格，从左上角出发，每次只能向下或向右移动，目标是到达右下角并使路径上的数字之和最小。

AdsGo AI

全自动 AI 广告专家，助您在数分钟内完成广告搭建、优化及扩量

下载

问题描述

动态规划思路

• 状态定义： dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和。
• 状态转移方程：
  • 如果 i > 0 且 j > 0：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
  • 如果 i == 0 且 j > 0：只能从左来，dp[i][j] = grid[i][j] + dp[i][j-1]
  • 如果 j == 0 且 i > 0：只能从上来，dp[i][j] = grid[i][j] + dp[i-1][j]
• 初始状态： dp[0][0] = grid[0][0]

C++ 实现代码

#include 
#include 
#include 
using namespace std;

int minPathSum(vector>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size();
    int n = grid[0].size();

    // 创建 dp 表，可以用原数组优化空间
    vector> dp(m, vector(n));
    dp[0][0] = grid[0][0];

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

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

    // 填充其余状态
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }

    return dp[m-1][n-1];
}

// 测试示例
int main() {
    vector> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    cout << "最小路径和: " << minPathSum(grid) << endl; // 输出 7
    return 0;
}

空间优化版本

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