动态规划核心原理动态规划dp是一种用空间换时间、用子问题解父问题的思想。例题1爬楼梯一维线性DP入门必练题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶第一步定义dp数组/状态dp[i]爬到第i阶楼梯的不同方法数。这里i从1开始和题目中的“n阶”对应更直观第二步推导状态转移方程要爬到第i阶有两种途径每次都要达到第i阶每次选择都是1或2步最后一次的选择分为两种情况每次情况下都是之前循环算好的方案数从第i-1阶爬1个台阶上来方法数等于dp[i-1]从第i-2阶爬2个台阶上来方法数等于dp[i-2]因此总方法数是两种途径的和状态转移方程dp[i] dp[i-1] dp[i-2]第三步初始化边界条件当i1时只有1种方法爬1个台阶所以dp[1] 1当i2时有2种方法11、2所以dp[2] 2注如果i从0开始dp[0]1表示爬到0阶有一种方法不爬dp[1]1结果一致可根据个人习惯选择第四步部分代码例题201背包经典面试题二维DP入门题目有n件物品和一个容量为v的背包。每件物品只能使用一次第i件物品的重量是weight[i]价值是value[i]。求将哪些物品装入背包可使这些物品的总重量不超过背包容量且总价值最大。示例n3v4weight[1,3,4]value[15,20,30]求最大价值。第一步定义dp数组/状态dp[i][j]前i件物品从第1件到第i件放入容量为j的背包中能获得的最大价值。i从1开始对应物品编号j从0开始对应背包容量第二步推导状态转移方程对于第i件物品有两种选择装或不装取两种选择的最大值。不装第i件物品最大价值 前i-1件物品放入容量j的背包的最大价值即dp[i-1][j]装第i件物品前提是背包容量j ≥ 物品i的重量weight[i-1]因为Python列表从0索引此时最大价值 前i-1件物品放入容量j-weight[i-1]的背包的最大价值 物品i的价值value[i-1]即dp[i-1][j - weight[i-1]] value[i-1]因此状态转移方程当j weight[i-1]$$dp[i][j] dp[i-1][j]$$装不下只能不装当j ≥ weight[i-1]$$dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i-1]] value[i-1])$$第三步初始化边界条件当i0前0件物品即没有物品无论背包容量j是多少最大价值都是0所以dp[0][j] 0j从0到v当j0背包容量为0无论有多少件物品都装不下最大价值都是0所以dp[i][0] 0i从0到n第四步确定遍历顺序有两个遍历维度物品i从1到n和背包容量j从1到v。遍历顺序先遍历物品再遍历背包容量也可以先遍历背包再遍历物品不影响结果但先遍历物品更直观。注意背包容量j要从1到v遍历正序因为01背包中每件物品只能用一次正序遍历不会重复使用物品第五步部分代码刷题路线从易到难入门爬楼梯、斐波那契数列一维线性DP基础打家劫舍、最小路径和二维线性DP进阶01背包、完全背包、多重背包背包DP提升最长递增子序列、最长公共子序列区间DP面试高频二叉树的最大路径和树形DP、编辑距离区间DP。