c++中如何实现动态规划最小路径和_c++动态规划最小路径和实现方法-C++-PHP中文网

最小路径和可通过动态规划求解，定义dpi为从起点到(i,j)的最小和，状态转移方程为dpi=gridi+min(dpi-1,dpi)，初始化第一行和第一列后遍历填充，最终结果为dpm-1。

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

在C++中实现动态规划求解“最小路径和”问题，通常应用于二维网格中从左上角到右下角的路径选择。目标是找出一条路径，使得路径上所有数字的和最小，每次只能向下或向右移动。

问题描述

给定一个 m × n 的非负整数网格 grid，找出从左上角到右下角的路径，使得路径上的数字总和最小。只能向下或向右移动。

动态规划思路

使用动态规划来避免重复计算。定义 dp[i][j] 表示从起点 (0,0) 到位置 (i,j) 的最小路径和。状态转移方程：

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

边界处理：

第一行：只能从左向右走，dp[0][j] = dp[0][j-1] + grid[0][j]
第一列：只能从上向下走，dp[i][0] = dp[i-1][0] + grid[i][0]

C++ 实现代码

可以直接在原数组上修改以节省空间，或者创建一个新的 dp 数组。以下是使用原数组进行空间优化的版本：

代码示例：

Neon AI

Neon AI帮助开发人员创建会话式AI应用程序和设备

下载

#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();

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

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

    // 填充其余位置
    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> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    cout << "最小路径和: " << minPathSum(grid) << endl;
    return 0;
}