动态规划DP 自我提问模板-程序员充电站

在面对动态规划问题时，建立一个系统的思考框架能大大提升解题效率。本文以 LeetCode 64 题为例，展示如何用"自我提问模板"梳理 DP 思路，并在实战中验证其有效性。

什么是动态规划自我提问模板？

动态规划的本质是"记忆化递归 + 最优子结构"，但很多时候我们会在定义状态、推导转移方程时感到困惑。为了更系统地分析 DP 问题，我总结了一套"自我提问模板"，包含以下关键要素：

dp[i][j] 定义：明确每个状态代表什么
默认值：初始化的边界条件
外部遍历：如何遍历整个状态空间
choice：在每个状态下有哪些选择（如果适用）
cost：每个选择的代价（如果适用）
转移条件：什么情况下进行状态转移
转移方程：如何从子问题推导到当前问题
返回值：最终答案在状态空间的哪个位置

我的思路 dp[i][j]定义：dp 和 grid 大小相同，dp[i][j]表示对应走到 grid[i][j]的最小sum 默认值：dp[0][0]=grid[0][0]外部遍历：遍历 grid，i 为行，j 为列，跳过 i=0，j=0choice: N/A cost: N/A 转移条件：N/A 转移方程：i=0: dp[i][j]=dp[i][j-1]+ grid[i][j]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])返回值：dp[gridSize][gridColSize[gridSize -1]]行的最小值

实战案例：LeetCode 64. Minimum Path Sum

题目描述

给定一个 m x n 的网格 grid，每个格子里是一个非负整数。从左上角 (0,0) 出发，只能向右或向下移动，走到右下角 (m-1, n-1)。要求找到一条路径，使路径上所有格子数字之和最小，并返回这个最小和。

使用模板分析

1. dp[i][j] 定义

dp 和 grid 大小相同，dp[i][j] 表示对应走到 grid[i][j] 的最小sum

这个定义很直观：我们需要知道"到达每个格子时的最小路径和"，因此 dp[i][j] 就表示从起点 (0,0) 走到位置 (i,j) 的最小路径和。

2. 默认值

dp[0][0] = grid[0][0]

起点是我们的初始状态，它的最小路径和就是起点格子本身的值。

3. 外部遍历

遍历 grid，i 为行，j 为列，跳过 i = 0，j = 0

我们需要填充整个 dp 数组，按行列顺序遍历。由于起点已经初始化，可以跳过 (0,0)。

4. choice & cost

N/A

在这道题中，我们不需要显式地考虑"选择"和"代价"的概念，因为路径是确定性的：只能向右或向下走，没有多个选择需要对比。

5. 转移条件

N/A

这道题的转移是无条件的，每个格子都需要根据其左边和上边的格子更新。

6. 转移方程

i = 0: dp[i][j] = dp[i][j-1] + grid[i][j] // 第一行只能从左边来 j = 0: dp[i][j] = dp[i-1][j] + grid[i][j] // 第一列只能从上边来 else: dp[i][j] = min(dp[i][j-1] + grid[i][j], dp[i-1][j] + grid[i][j]) // 其他位置取左边和上边的最小值

这个转移方程体现了 DP 的核心：

对于第一行（i=0），只能从左边走过来
对于第一列（j=0），只能从上边走过来
对于其他位置，可以从左边或上边过来，我们选择路径和更小的那条

7. 返回值

注意：原始思路写的是"dp[gridSize][gridColSize[gridSize - 1]] 行的最小值"，这是错误的！

正确的返回值应该是：dp[gridSize-1][gridColSize[gridSize-1]-1]

即右下角那个格子的值，因为题目要求必须走到右下角，而不是最后一行的任意位置。

C 语言代码实现

#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 数组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];// 遍历整个 gridfor(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];else// 其他位置：取左边和上边的最小值dp[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;}