本文整理这道题的题意、思路推导、状态设计、边界处理，以及一份 C 语言实现，并顺带对一些容易在面试中被问到的细节做说明。leetcode+1
题目理解
给定一个 m x n 的网格 grid，每个格子里是一个非负整数。leetcode
从左上角 (0,0) 出发，只能向右或向下移动，走到右下角 (m-1, n-1)。leetcode
要求：找到一条路径，使路径上所有格子数字之和最小，并返回这个最小和。leetcode
示例：
grid = [[1,3,1],[1,5,1],[4,2,1]]，答案为 7，路径为 1 → 3 → 1 → 1 → 1。leetcode
grid = [[1,2,3],[4,5,6]]，答案为 12。leetcode
约束：
1 <= m, n <= 200，0 <= grid[i][j] <= 200。leetcode
动态规划思路推导
1. 状态定义
设一个与 grid 同大小的二维数组 dp：
状态含义：dp[i][j] 表示从起点 (0,0) 走到格子 (i,j) 的最小路径和。
这样，最终目标就是求 dp[m-1][n-1]。
2. 状态转移
从起点往终点推导每个格子的最小路径和：
起点：
dp[0][0] = grid[0][0]
第一行 i == 0：
只能从左边走过来：
dp[0][j] = dp[0][j-1] + grid[0][j]
第一列 j == 0：
只能从上边走过来：
dp[i][0] = dp[i-1][0] + grid[i][0]
其他位置 (i > 0, j > 0)：
只能从上方 (i-1,j) 或左方 (i,j-1) 过来，取路径和较小的那条：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
这正好对应你一开始写下的转移方程，思路是正确的，只是最后返回值当时写成了"最后一行的最小值"，与题目"必须到右下角"不一致，后面你在代码中已经修正为右下角坐标。leetcode
边界与实现细节
1. 初始化与默认值
在 C 代码中，为了方便统一转移，你给 dp 初始填了一个很大的值 INF_MAX = 0x7fffffff：
#defineINF_MAX0x7fffffff然后 dp[i][j] 全部初始化为 INF_MAX，再从 (0,0) 开始，用转移公式迭代更新。
实际上这道题因为边界（i == 0 和 j == 0）单独处理了，INF_MAX 更多是防御性初始化，可以保留，也可以不依赖它来写逻辑。leetcode
2. 边界跳过起点
代码里：
if(i==0&&j==0)continue;对 (0,0) 直接跳过，是因为已经单独设定了 dp[0][0] = grid[0][0]，避免在转移时又被覆盖或访问到负索引。
这在面试时是加分点：说明清楚起点是"手动初始化"，循环里只处理除起点外的其他格子。leetcode
C 语言代码实现
下面是你提交并 AC 的 C 代码，时间 0ms，击败 100%，逻辑清晰、边界正确、空间也正常释放了内存。leetcode
#include<stdlib.h>#defineINF_MAX0x7fffffff#defineMIN(a,b)((a)<(b)?(a):(b))intminPathSum(int**grid,intgridSize,int*gridColSize){inti,j,result,col_size;int**dp;dp=(int**)malloc(gridSize*sizeof(int*));for(i=0;i<gridSize;i++){col_size=gridColSize[i];dp[i]=(int*)malloc(col_size*sizeof(int));for(j=0;j<col_size;j++)dp[i][j]=INF_MAX;}dp[0][0]=grid[0][0];for(i=0;i<gridSize;i++){col_size=gridColSize[i];for(j=0;j<col_size;j++){if(i==0&&j==0)continue;if(i==0)dp[i][j]=dp[i][j-1]+grid[i][j];elseif(j==0)dp[i][j]=dp[i-1][j]+grid[i][j];elsedp[i][j]=MIN(dp[i][j-1]+grid[i][j],dp[i-1][j]+grid[i][j]);}}col_size=gridColSize[gridSize-1];result=dp[gridSize-1][col_size-1];for(i=0;i<gridSize;i++)free(dp[i]);free(dp);returnresult;}复杂度分析：
时间复杂度：遍历整张表一次，O(mn)。
空间复杂度：使用了一个与 grid 同大小的 dp 数组，O(mn) 额外空间。leetcode
可能的面试追问与优化方向
能否不使用额外二维 dp 数组，直接在 grid 上原地累加，从而把额外空间从 O(mn) 优化到 O(1)？leetcode
如果只用一维数组（按行或按列滚动），如何写状态转移，空间复杂度可以优化到 O(min(m,n))？leetcode
https://leetcode.com/problems/minimum-path-sum/?envType=study-plan-v2&envId=top-interview-150
https://leetcode.com/problems/minimum-path-sum/description/?envType=study-plan-v2&envId=top-interview-150
https://leetcode.com/problems/minimum-path-sum/submissions/1871120418/?envType=study-plan-v2&envId=top-interview-150
