一、动态规划核心思想动态规划DP是一种通过分解子问题并存储子问题解来避免重复计算的算法思想。它适用于具有最优子结构和重叠子问题特性的问题。最优子结构 问题的最优解包含子问题的最优解重叠子问题 子问题会被重复计算需要缓存解题四步骤图解法步骤说明1. 定义状态确定DP数组含义dp[i]或dp[i][j]2. 初始化与边界设置边界条件确定初始条件和边界情况表格第一行/列3. 找状态转移方程找出状态之间的关系推导递推公式定义如何从已知状态推导未知状态箭头表示依赖关系4. 计算顺序计算最优解的值确定填表方向自底向上或自顶向下5.构造解利用计算出来的信息构造一个最优解如果我们仅仅需要一个最优解而非解本身可以忽略此步骤二、经典问题图解 Java实现1. 斐波那契数列入门状态转移图dp[0] 0 dp[1] 1 dp[2] dp[1] dp[0] 1 ←──┐ dp[3] dp[2] dp[1] 2 ←─┼── 每个状态依赖前两个状态 dp[4] dp[3] dp[2] 3 ←─┘Java实现publicintfib(intn){if(n1)returnn;int[]dpnewint[n1];dp[0]0;dp[1]1;// 自底向上填表for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}// 空间优化版滚动数组publicintfibOptimized(intn){if(n1)returnn;intpre0,curr1;for(inti2;in;i){intsumprecurr;precurr;currsum;}returncurr;}2. 0-1背包问题二维DP图解问题背包容量4磅物品如下求最大价值物品重量价值吉他(G)11500音响(S)43000电脑(L)32000填表过程可视化物品\容量0磅1磅2磅3磅4磅无00000吉他01500(G)1500(G)1500(G)1500(G)音响01500(G)1500(G)1500(G)3000(S)电脑01500(G)1500(G)2000(L)3500(GL)关键决策点4磅列不放电脑dp[2][4] 3000音响放电脑2000 dp[2][1](1500) 3500取最大值3500Java实现publicclassKnapsackProblem{publicstaticvoidmain(String[]args){int[]val{0,1500,3000,2000};// 商品价值前面补0方便计算int[]w{0,1,4,3};// 商品重量intm4;// 背包容量intnval.length;// 物品个数int[][]dpnewint[n][m1];// 填表i-物品, j-容量for(inti1;in;i){for(intj1;jm;j){if(w[i]j){// 当前物品太重装不下继承上一个状态dp[i][j]dp[i-1][j];}else{// 比较不放 vs 放当前价值剩余空间价值intnotPutdp[i-1][j];intputval[i]dp[i-1][j-w[i]];dp[i][j]Math.max(notPut,put);}}}System.out.println(最大价值: dp[n-1][m]);// 3500}}3. 三角形最小路径和树形图解问题结构2 ← 起点 / \ 3 4 / \ / \ 6 5 7 / \ / \ / \ 4 1 8 3 ← 终点DP思路自底向上每个节点的最小路径 自身值 min(左下, 右下)Java实现publicintminimumTotal(ListListIntegertriangle){intntriangle.size();// dp[i][j] 表示从(i,j)到底边的最小路径和int[][]dpnewint[n][n];// 初始化底边for(intj0;jn;j){dp[n-1][j]triangle.get(n-1).get(j);}// 自底向上填表for(intin-2;i0;i--){for(intj0;ji;j){dp[i][j]triangle.get(i).get(j)Math.min(dp[i1][j],dp[i1][j1]);}}returndp[0][0];// 顶点即为答案}4. 不同路径网格DP图解问题m×n网格从左上到右下只能向右或向下走状态转移图start → → → → ↓ ↓ ↓ → → → ↓ ↓ ↓ ↓ → → → end dp[i][j] dp[i-1][j] dp[i][j-1] // 从上或从左来Java实现publicintuniquePaths(intm,intn){int[][]dpnewint[m][n];// 初始化第一行和第一列只有一条路径for(inti0;im;i)dp[i][0]1;for(intj0;jn;j)dp[0][j]1;// 填表for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m-1][n-1];}三、可视化工具推荐Algorithm Visualizer- 可交互查看DP填表过程VisuAlgo- 支持多种算法的可视化演示DP Visualization Project- 专门用于动态规划的JavaScript可视化工具四、学习建议从斐波那契开始- 理解记忆化搜索 vs 递推的区别画表格- 手动填表理解状态转移如背包问题找状态转移方程- 这是DP的核心难点空间优化- 掌握滚动数组技巧如只保留两行/两列需要我针对某个具体问题进行更详细的图解说明吗
动态规划（Dynamic Programming）
发布时间：2026/6/27 8:11:06
一、动态规划核心思想动态规划DP是一种通过分解子问题并存储子问题解来避免重复计算的算法思想。它适用于具有最优子结构和重叠子问题特性的问题。最优子结构 问题的最优解包含子问题的最优解重叠子问题 子问题会被重复计算需要缓存解题四步骤图解法步骤说明1. 定义状态确定DP数组含义dp[i]或dp[i][j]2. 初始化与边界设置边界条件确定初始条件和边界情况表格第一行/列3. 找状态转移方程找出状态之间的关系推导递推公式定义如何从已知状态推导未知状态箭头表示依赖关系4. 计算顺序计算最优解的值确定填表方向自底向上或自顶向下5.构造解利用计算出来的信息构造一个最优解如果我们仅仅需要一个最优解而非解本身可以忽略此步骤二、经典问题图解 Java实现1. 斐波那契数列入门状态转移图dp[0] 0 dp[1] 1 dp[2] dp[1] dp[0] 1 ←──┐ dp[3] dp[2] dp[1] 2 ←─┼── 每个状态依赖前两个状态 dp[4] dp[3] dp[2] 3 ←─┘Java实现publicintfib(intn){if(n1)returnn;int[]dpnewint[n1];dp[0]0;dp[1]1;// 自底向上填表for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}// 空间优化版滚动数组publicintfibOptimized(intn){if(n1)returnn;intpre0,curr1;for(inti2;in;i){intsumprecurr;precurr;currsum;}returncurr;}2. 0-1背包问题二维DP图解问题背包容量4磅物品如下求最大价值物品重量价值吉他(G)11500音响(S)43000电脑(L)32000填表过程可视化物品\容量0磅1磅2磅3磅4磅无00000吉他01500(G)1500(G)1500(G)1500(G)音响01500(G)1500(G)1500(G)3000(S)电脑01500(G)1500(G)2000(L)3500(GL)关键决策点4磅列不放电脑dp[2][4] 3000音响放电脑2000 dp[2][1](1500) 3500取最大值3500Java实现publicclassKnapsackProblem{publicstaticvoidmain(String[]args){int[]val{0,1500,3000,2000};// 商品价值前面补0方便计算int[]w{0,1,4,3};// 商品重量intm4;// 背包容量intnval.length;// 物品个数int[][]dpnewint[n][m1];// 填表i-物品, j-容量for(inti1;in;i){for(intj1;jm;j){if(w[i]j){// 当前物品太重装不下继承上一个状态dp[i][j]dp[i-1][j];}else{// 比较不放 vs 放当前价值剩余空间价值intnotPutdp[i-1][j];intputval[i]dp[i-1][j-w[i]];dp[i][j]Math.max(notPut,put);}}}System.out.println(最大价值: dp[n-1][m]);// 3500}}3. 三角形最小路径和树形图解问题结构2 ← 起点 / \ 3 4 / \ / \ 6 5 7 / \ / \ / \ 4 1 8 3 ← 终点DP思路自底向上每个节点的最小路径 自身值 min(左下, 右下)Java实现publicintminimumTotal(ListListIntegertriangle){intntriangle.size();// dp[i][j] 表示从(i,j)到底边的最小路径和int[][]dpnewint[n][n];// 初始化底边for(intj0;jn;j){dp[n-1][j]triangle.get(n-1).get(j);}// 自底向上填表for(intin-2;i0;i--){for(intj0;ji;j){dp[i][j]triangle.get(i).get(j)Math.min(dp[i1][j],dp[i1][j1]);}}returndp[0][0];// 顶点即为答案}4. 不同路径网格DP图解问题m×n网格从左上到右下只能向右或向下走状态转移图start → → → → ↓ ↓ ↓ → → → ↓ ↓ ↓ ↓ → → → end dp[i][j] dp[i-1][j] dp[i][j-1] // 从上或从左来Java实现publicintuniquePaths(intm,intn){int[][]dpnewint[m][n];// 初始化第一行和第一列只有一条路径for(inti0;im;i)dp[i][0]1;for(intj0;jn;j)dp[0][j]1;// 填表for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m-1][n-1];}三、可视化工具推荐Algorithm Visualizer- 可交互查看DP填表过程VisuAlgo- 支持多种算法的可视化演示DP Visualization Project- 专门用于动态规划的JavaScript可视化工具四、学习建议从斐波那契开始- 理解记忆化搜索 vs 递推的区别画表格- 手动填表理解状态转移如背包问题找状态转移方程- 这是DP的核心难点空间优化- 掌握滚动数组技巧如只保留两行/两列需要我针对某个具体问题进行更详细的图解说明吗
