最小路径和可通过动态规划求解，定义dpi为从(0,0)到(i,j)的最小路径和，状态转移方程根据边界条件分三种情况，初始化第一行和第一列后，递推填充其余位置，最终结果为dpm-1；空间优化版本使用一维数组将空间复杂度降为O(n)，按行更新dp值，核心逻辑不变。
在C++中实现动态规划求解“最小路径和”问题，通常针对一个二维网格，从左上角出发，每次只能向下或向右移动，目标是到达右下角并使路径上的数字之和最小。
问题描述
给定一个 m × n 的非负整数网格 grid，找出一条从左上角到右下角的路径，使得路径上所有数字的和最小。每次只能向下或向右移动。动态规划思路
使用动态规划的关键是定义状态和状态转移方程：- 状态定义： 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++ 实现代码
以下是一个完整、清晰的 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>}
空间优化版本
可以只用一维数组优化空间复杂度到 O(n)：
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>}
基本上就这些。核心是理解状态转移逻辑，然后按行或按列递推即可。 
