动态规划核心原理：
动态规划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]
第三步：初始化边界条件
当i=1时，只有1种方法（爬1个台阶），所以dp[1] = 1；
当i=2时，有2种方法（1+1、2），所以dp[2] = 2；
（注：如果i从0开始，dp[0]=1（表示爬到0阶，有一种方法：不爬），dp[1]=1，结果一致，可根据个人习惯选择）
第四步：部分代码
例题2：01背包（经典面试题，二维DP入门）
题目：有n件物品和一个容量为v的背包。每件物品只能使用一次，第i件物品的重量是weight[i]，价值是value[i]。求将哪些物品装入背包，可使这些物品的总重量不超过背包容量，且总价值最大。
示例：n=3，v=4，weight=[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])$$
第三步：初始化边界条件
当i=0（前0件物品，即没有物品）：无论背包容量j是多少，最大价值都是0，所以dp[0][j] = 0（j从0到v）；
当j=0（背包容量为0）：无论有多少件物品，都装不下，最大价值都是0，所以dp[i][0] = 0（i从0到n）；
第四步：确定遍历顺序
有两个遍历维度：物品i（从1到n）和背包容量j（从1到v）。
遍历顺序：先遍历物品，再遍历背包容量（也可以先遍历背包再遍历物品，不影响结果，但先遍历物品更直观）。
注意：背包容量j要从1到v遍历（正序），因为01背包中每件物品只能用一次，正序遍历不会重复使用物品
第五步：部分代码
刷题路线（从易到难）：
入门：爬楼梯、斐波那契数列（一维线性DP）；
基础：打家劫舍、最小路径和（二维线性DP）；
进阶：01背包、完全背包、多重背包（背包DP）；
提升：最长递增子序列、最长公共子序列（区间DP）；
面试高频：二叉树的最大路径和（树形DP）、编辑距离（区间DP）。
