Java 算法实践（七）：动态规划

这回溯算法本质上是一种暴力的穷举搜索，它遍历了问题的所有可能性（状态空间树）。然而，在许多问题中，回溯搜索会产生大量的重叠子问题，导致计算资源的极度浪费。

动态规划（Dynamic Programming, DP） 动态规划并非一种具体的算法，而是一种数学优化的思维方式。是一种通过将复杂问题分解为子问题，并存储子问题的解以避免重复计算的算法技术。它与分治法（Divide and Conquer）的区别在于：分治法的子问题通常是独立的（如归并排序），而动态规划的子问题是重叠的。

DP 的核心思想是空间换时间。通过维护一个表格（Table，通常是数组）来记录已经计算过的状态，将指数级的时间复杂度优化为多项式级（通常是线性或平方级）。

一、 从递归到动态规划：思维演进

理解 DP 的最佳路径是从斐波那契数列（Fibonacci）开始。虽然这是一个简单的数学问题，但它完美展示了算法复杂度的演变。

1.1 暴力递归

斐波那契数列定义： f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1) + f(n-2) f(n)=f(n−1)+f(n−2)。

intfib(int n){if(n <=1)return n;returnfib(n -1)+fib(n -2);}

分析：
该算法的执行流程是一棵二叉树。计算 f ( 20 ) f(20) f(20) 需要计算 f ( 19 ) f(19) f(19) 和 f ( 18 ) f(18) f(18)，而计算 f ( 19 ) f(19) f(19) 又需要计算 f ( 18 ) f(18) f(18) 和 f ( 17 ) f(17) f(17)。

• 重叠计算： f ( 18 ) f(18) f(18) 被重复计算了多次。随着 n n n 增大，重复计算呈指数级爆炸。
• 复杂度： O ( 2 n ) O(2^n) O(2n)。当 n = 50 n=50 n=50 时，计算量将达到千万亿级，程序会超时。

1.2 记忆化搜索

为了解决重复计算，我们可以引入一个“备忘录”（Memo），即一个数组或哈希表。每次计算 f ( n ) f(n) f(n) 前，先查表；计算完后，将结果存入表。

int[] memo;publicintfib(int n){ memo =newint[n +1];returnhelper(n);}inthelper(int n){if(n <=1)return n;// 查表：如果计算过，直接返回if(memo[n]!=0)return memo[n];// 如果没有计算过，计算并存表 memo[n]=helper(n -1)+helper(n -2);return memo[n];}

分析：

• 剪枝：递归树中的重复分支被剪除。
• 复杂度：每个子问题只计算一次，总耗时 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)（递归栈 + 数组）。

1.3 动态规划

记忆化搜索依然保留了递归调用的栈开销。动态规划则是自底向上的迭代。不再需要递归函数，而是直接通过循环填充数组。

publicintfib(int n){if(n <=1)return n;// 状态定义：dp[i] 表示第 i 个斐波那契数int[] dp =newint[n +1];// 初始化 dp[0]=0; dp[1]=1;// 状态转移：从已知推导未知for(int i =2; i <= n; i++){ dp[i]= dp[i -1]+ dp[i -2];}return dp[n];}

分析：
这是标准的 DP 形态。它消除了递归栈的风险，且逻辑清晰。

1.4 空间优化

观察转移方程 d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i-1] + dp[i-2] dp[i]=dp[i−1]+dp[i−2]，可以发现：计算当前状态只依赖于前两个状态。因此，不需要维护整个数组，只需两个变量即可。

publicintfib(int n){if(n <=1)return n;int prev2 =0, prev1 =1;for(int i =2; i <= n; i++){int curr = prev1 + prev2; prev2 = prev1; prev1 = curr;}return prev1;}

分析：
空间复杂度降低至 O ( 1 ) O(1) O(1)。这种技巧在 DP 问题中非常通用。

二、 线性 DP：一维状态链

线性 DP 是动态规划中最基础的模型。其特征是：问题可以被分解为线性排列的子问题，状态 dp[i] 的值通常仅依赖于 dp[i-1]、dp[i-2] 等前几个状态。

解决线性 DP 的关键在于下标对齐。需要明确 dp[i] 中的 i 到底代表什么，这直接决定了数组的大小、初始化的边界以及循环的起点。

2.1 实战例题：爬楼梯

题目链接：LeetCode 70. Climbing Stairs

题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

逻辑深度解析：

1. 状态定义：
   题目描述中的楼梯层数是 1 到 n n n。为了直观映射，我们定义 d p [ i ] dp[i] dp[i] 为 到达第 i i i 阶楼梯的方法总数。
2. 数组大小选择：
   由于要计算的是第 n n n 阶，即需要访问 d p [ n ] dp[n] dp[n]。在 Java 数组中，要使下标 n n n 合法，数组长度必须至少为 n + 1 n + 1 n+1。因此声明 int[] dp = new int[n + 1]。其中 dp[0] 是占位符，无实际物理意义（或理解为站在地面，无需走动，意义不大）。
3. 推导转移方程：
   到达第 i i i 阶只有两种可能：
   • 从第 i − 1 i-1 i−1 阶向上爬 1 阶。
   • 从第 i − 2 i-2 i−2 阶向上爬 2 阶。
     因此： d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i-1] + dp[i-2] dp[i]=dp[i−1]+dp[i−2]。
4. 初始化与循环起点：
   根据方程，计算 d p [ i ] dp[i] dp[i] 需要依赖前两项。因此， i = 1 i=1 i=1 和 i = 2 i=2 i=2 不能通过方程计算（会造成下标越界或无意义），必须人为设定：
   • d p [ 1 ] = 1 dp[1] = 1 dp[1]=1：到达第 1 阶只有 1 种方法（1）。
   • d p [ 2 ] = 2 dp[2] = 2 dp[2]=2：到达第 2 阶有 2 种方法（1+1 或 2）。
   • 循环起点：因为 1 和 2 已知，推导从第 3 阶开始，即 i = 3。

Java 代码：

publicintclimbStairs(int n){// 边界条件：如果只有 1 阶或 2 阶，直接返回 n 即可，无需建表if(n <=2)return n;// 数组大小：n + 1// 目的是为了让 dp[i] 直接对应“第 i 阶”，避免 i-1 的思维转换int[] dp =newint[n +1];// 初始化 dp[1]=1; dp[2]=2;// 状态转移// 从第 3 阶开始计算，一直计算到第 n 阶for(int i =3; i <= n; i++){ dp[i]= dp[i -1]+ dp[i -2];}// 返回第 n 阶的结果return dp[n];}

2.2 实战例题：打家劫舍

题目链接：LeetCode 198. House Robber

题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金 nums[i]，相邻的房屋装有防盗系统，不可同时被偷。求最高金额。

逻辑深度解析：

与爬楼梯不同，本题输入的是一个数组 nums，其下标从 0 到 n − 1 n-1 n−1。

1. 状态定义：
   为了与输入数组 nums 的下标保持一致，定义 d p [ i ] dp[i] dp[i] 为 考虑前 i + 1 i + 1 i+1 间房屋（即下标范围 0 … i 0 \dots i 0…i）所能获得的最高金额。
2. 数组大小选择：
   输入数组长度为 n n n，要计算的最终结果是考虑所有房屋（即下标 n − 1 n-1 n−1）。因此 dp 数组长度设为 n n n 即可，下标范围 0 … n − 1 0 \dots n-1 0…n−1 与 nums 完全对齐。
3. 推导转移方程：
   对于下标为 i i i 的房屋，有两种决策：
   • 方案 A（偷第 i i i 间）：前提是第 i − 1 i-1 i−1 间不能偷。那么最大金额 = 第 i i i 间的钱 + 考虑前 i − 2 i-2 i−2 间房屋的最大金额。即 n u m s [ i ] + d p [ i − 2 ] nums[i] + dp[i-2] nums[i]+dp[i−2]。
   • 方案 B（不偷第 i i i 间）：那么最大金额 = 考虑前 i − 1 i-1 i−1 间房屋的最大金额（即保持之前的最优解）。即 d p [ i − 1 ] dp[i-1] dp[i−1]。
   • 决策：取两者最大值。 d p [ i ] = max ⁡ ( d p [ i − 1 ] , n u m s [ i ] + d p [ i − 2 ] ) dp[i] = \max(dp[i-1], nums[i] + dp[i-2]) dp[i]=max(dp[i−1],nums[i]+dp[i−2])。
4. 初始化与循环起点：
   方程中涉及 i − 2 i-2 i−2，因此 i = 0 i=0 i=0 和 i = 1 i=1 i=1 必须单独初始化，防止越界：
   • d p [ 0 ] dp[0] dp[0]：只有第 0 间房。必然偷。值 = n u m s [ 0 ] nums[0] nums[0]。
   • d p [ 1 ] dp[1] dp[1]：有第 0、1 间房。不能同时偷，只能偷其中金额大的那间。值 = max ⁡ ( n u m s [ 0 ] , n u m s [ 1 ] ) \max(nums[0], nums[1]) max(nums[0],nums[1])。
   • 循环起点：从下标 2 开始，即 i = 2。

Java 代码：

publicintrob(int[] nums){// 边界检查：空数组或长度为 0if(nums ==null|| nums.length ==0)return0;// 只有一间房，直接偷if(nums.length ==1)return nums[0];int n = nums.length;// 数组大小：n// dp[i] 对应 nums[0...i] 的计算结果int[] dp =newint[n];// 初始化 dp[0]= nums[0];// 对于第二间房，最大收益是两间房中较大的那个，而不是 nums[1] dp[1]=Math.max(nums[0], nums[1]);// 状态转移// 从下标 2 开始遍历到 n-1for(int i =2; i < n; i++){// 偷 i: nums[i] + dp[i-2]// 不偷 i: dp[i-1] dp[i]=Math.max(dp[i -1], nums[i]+ dp[i -2]);}// 最终状态存储在数组最后一个位置return dp[n -1];}

2.3 如何确定数组大小与循环起点？

通过这两个例题可以看出，DP 数组的构建方式完全服务于状态的定义。

所以 打家劫舍 题目中也完全可以使用类似 爬楼梯 的定义方式。即使用 dp[n+1] 数组，其中 dp[i] 表示考虑前 i 间房屋（下标范围 0 … i − 1 0 \dots i-1 0…i−1）所能获得的最高金额。这种方式更注重“前 0 间房屋”的边界（dp[0] = 0），最终结果为 dp[n]。

1. 状态定义： d p [ i ] dp[i] dp[i] = 考虑前 i 间房屋的最大金额。
2. 转移方程： d p [ i ] = m a x ⁡ ( d p [ i − 1 ] , n u m s [ i − 1 ] + d p [ i − 2 ] ) dp[i]=max⁡(dp[i−1],nums[i−1]+dp[i−2]) dp[i]=max⁡(dp[i−1],nums[i−1]+dp[i−2])（注意 nums 下标调整为 i-1）。
3. 初始化： d p [ 0 ] = 0 dp[0] = 0 dp[0]=0（无房屋）； d p [ 1 ] = n u m s [ 0 ] dp[1] = nums[0] dp[1]=nums[0]（只有第一间）。
4. 循环起点：从 i = 2 开始。

Java 代码

publicintrob(int[] nums){// 边界检查if(nums ==null|| nums.length ==0)return0;int n = nums.length;if(n ==1)return nums[0];// 数组大小：n + 1int[] dp =newint[n +1];// 初始化 dp[0]=0;// 前0间房屋 dp[1]= nums[0];// 前1间房屋// 状态转移for(int i =2; i <= n; i++){// 偷第 i-1 间: nums[i-1] + dp[i-2]// 不偷: dp[i-1] dp[i]=Math.max(dp[i -1], nums[i -1]+ dp[i -2]);}// 最终结果：前 n 间房屋return dp[n];}

三、 背包模型：组合与最值

背包问题（Knapsack Problem）是线性 DP 的一个特殊分支，其核心特征是：给定一组物品（具有价值与体积）和一个容器（有限容量），决策如何选择物品以达成目标。

最常见的两类背包模型是：

1. 完全背包：每个物品可以被选择无限次。
2. 0/1 背包：每个物品只能被选择一次（要么选，要么不选）。

这两类问题在代码结构上极度相似，唯一的区别在于内层循环的遍历方向。理解这一点是掌握背包问题的关键。

3.1 实战例题：零钱兑换（完全背包求最值）

题目链接：LeetCode 322. Coin Change

题目描述：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。每种硬币的数量是无限的。

逻辑深度解析：

1. 模型识别：
   硬币数量无限，意味着可以重复选择同一个面额。这是一个标准的完全背包问题。
2. 状态定义：
   d p [ i ] dp[i] dp[i] 表示凑齐金额 i i i 所需的最小硬币数量。
3. 状态转移方程：
   对于金额 i i i，可以遍历所有硬币面额 c c c。
   如果我们选择了面额 c c c，那么当前的硬币数就是 1（当前这枚）加上“凑齐剩余金额 i − c i-c i−c 的最小硬币数”。
   d p [ i ] = min ⁡ ( d p [ i ] , d p [ i − c ] + 1 ) dp[i] = \min(dp[i], dp[i - c] + 1) dp[i]=min(dp[i],dp[i−c]+1)
4. 初始化策略（求最小值的陷阱）：
   • d p [ 0 ] = 0 dp[0] = 0 dp[0]=0：凑齐 0 元不需要硬币。
   • d p [ 1 … a m o u n t ] dp[1 \dots amount] dp[1…amount]：由于我们在方程中使用了 Math.min，如果初始化为 0，所有结果都会被 0 覆盖。因此必须初始化为一个无效的大数值。
   • 注意：不要使用 Integer.MAX_VALUE，因为 dp[i-c] + 1 可能会导致整型溢出变成负数。推荐使用 amount + 1（即使全是 1 元硬币，数量也不会超过 amount，所以 amount + 1 等同于无穷大）。

Java 代码：

publicintcoinChange(int[] coins,int amount){// 定义 DP 数组// 长度设为 amount + 1，保证下标能取到 amountint[] dp =newint[amount +1];// 初始化// 使用 amount + 1 作为“无穷大”标记int max = amount +1;Arrays.fill(dp, max); dp[0]=0;// 状态转移// 外层循环：遍历所有可能的金额（背包容量）for(int i =1; i <= amount; i++){// 内层循环：遍历所有硬币（物品）for(int coin : coins){// 只有当当前金额 i 大于等于硬币面额 coin 时，才能使用该硬币if(i >= coin){// 核心方程：尝试放入 coin，看是否能使总数量变小// dp[i - coin] 是在当前层或之前层计算过的结果 0 <= i - coin <= i dp[i]=Math.min(dp[i], dp[i - coin]+1);}}}// 结果校验// 如果 dp[amount] 仍然是初始值，说明无法凑出return dp[amount]> amount ?-1: dp[amount];}

3.2 实战例题：分割等和子集（0/1 背包存在性问题）

题目链接：LeetCode 416. Partition Equal Subset Sum

题目描述：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

逻辑深度解析：

1. 问题转化：
   “分割成两个相等子集”等价于“从数组中选出若干个数，使其和恰好等于总和的一半”。
   设 Target = Sum / 2。
   问题转化为：能否装满容量为 Target 的背包？
   由于每个数字只能用一次，这是标准的0/1 背包问题（每个物品不可重复使用）。
2. 状态定义：
   • d p [ i ] dp[i] dp[i] 表示容量为 i i i 的背包能否被恰好填满（boolean 类型）。
   • 初始时，dp[0] = true（空背包总是能“填满”0），其他 dp[j] = false。
3. 核心难点：转移方程的推导与遍历顺序**
   • 转移方程的由来：
     • 对于每个数字 n u m num num，需要决定是否将其放入背包（容量 j j j）。
     • 如果不放 n u m num num： d p [ j ] dp[j] dp[j] 保持原值（即之前是否能填满 j j j，不受 n u m num num 影响）。
     • 如果放 n u m num num：前提是 j > = n u m j >= num j>=num（容量足够），则问题退化为“能否用之前的数字填满 j − n u m j - num j−num 的容量”，然后再加上 num 就正好填满 j j j。所以，这里需要用到 d p [ j − n u m ] dp[j - num] dp[j−num] —— 如果 d p [ j − n u m ] dp[j - num] dp[j−num] 为 true，说明之前能填满 j − n u m j - num j−num，现在加上 n u m num num 就能填满 j j j。
     • 综合决策：只要“不放”或“放”两种方式中任意一种可行，就设 d p [ j ] = t r u e dp[j] = true dp[j]=true。因此，方程是 d p [ j ] = d p [ j ] ∣ ∣ d p [ j − n u m ] dp[j] = dp[j] || dp[j - num] dp[j]=dp[j]∣∣dp[j−num]（如果 j >= num）。
     • 为什么需要 d p [ j − n u m ] dp[j - num] dp[j−num]？因为这是“决策的核心”——它代表了“减去当前物品后”的子问题结果，体现了 DP 的“子问题依赖”思想。如果没有这个，问题就无法分解为更小的子问题，导致无法逐步构建答案。
   • 一维数组的遍历顺序（为什么从大到小）：
     • 在 0/1 背包中，内层循环必须从大到小遍历（从 t a r g e t target target 到 n u m num num）。
     • 原因推导：
       • 正序遍历（从小到大）：计算 d p [ j ] dp[j] dp[j] 时，需要用到 d p [ j − n u m ] dp[j - num] dp[j−num]，但如果从左往右， d p [ j − n u m ] dp[j - num] dp[j−num] 可能已经被当前 num 更新过（相当于重复使用了 n u m num num），违背 0/1 原则（每个数字只能用一次）。
       • 示例：假设 num=3，target=6。从小到大：先更新 dp[3] = true（放 3），然后到 dp[6] 时，用 dp[6-3]=dp[3]（已包含 3），相当于用了两次 3，错误地认为能填满 6（3+3）。
       • 反序遍历（从大到小）：计算 d p [ j ] dp[j] dp[j] 时， d p [ j − n u m ] dp[j - num] dp[j−num] 还是“之前的状态”（未被当前 n u m num num 更新），确保 n u m num num 只被考虑一次。
       • 示例：从大到小，先更新 dp[6] 用 dp[3]（初始 false，不更新），然后更新 dp[3] 用 dp[0]=true → dp[3]=true。现在 dp[6] 仍 false（因为没其他数字支持第二次 3）。
     • 如果是完全背包（无限使用，如零钱兑换），则用正序遍历，以允许重复使用物品。

Java 代码：

publicbooleancanPartition(int[] nums){// 预处理：计算总和int sum =0;for(int num : nums){ sum += num;}// 如果总和是奇数，无法平分，直接返回 falseif(sum %2!=0)returnfalse;int target = sum /2;// 定义 DP 数组// dp[j] 表示是否能凑出和为 jboolean[] dp =newboolean[target +1];// 初始化 dp[0]=true;// 容量为 0 时，不选任何元素即为满，为 true// 状态转移// 外层循环：遍历物品（数字）for(int num : nums){// 内层循环：遍历背包容量；必须从大到小遍历 (target -> num)for(int i = target; i >= num; i--){// 如果不放入 num：状态保持 dp[i]// 如果放入 num：状态取决于 dp[i - num] dp[i]= dp[i]|| dp[i - num];}}return dp[target];}

3.3 总结：完全背包 vs 0/1 背包

在将背包问题优化为一维 DP 数组后，完全背包和 0/1 背包在代码结构上高度相似，主要差异体现在物品的可重复性和内层循环的遍历方向上。这直接决定了状态更新的逻辑，避免了重复计算或非法重复使用物品。

• 物品限制与适用场景：
  • 0/1 背包：每个物品（数字/硬币）只能选择一次，适合“一次性决策”的问题，如“分割等和子集”（LC 416），本质上是判断是否存在子集和等于目标值。
  • 完全背包：每个物品可以无限重复选择，适合“可复用资源”的问题，如“零钱兑换”（LC 322），本质上是求最小/最大/组合数等优化值。
• 背包容量循环方向：
  • 0/1 背包：从大到小遍历（target 到 num），以确保每个物品只被考虑一次。反序防止当前物品的更新影响后续决策，引用的是“未更新前的状态”（相当于上一层的结果）。
  • 完全背包：从小到大遍历（num 到 target），允许当前物品的更新被后续容量复用，引用的是“当前层已更新的状态”，从而实现无限重复选择。
• 物理含义与注意事项：
  • 0/1 背包：强调 互斥决策，转移时使用或操作 ( ∣ ∣ ) (||) (∣∣) 或 m a x / m i n max/min max/min 来合并“选/不选”的结果。如果顺序错乱，会导致物品被多次使用，违背问题约束。
  • 完全背包：强调 累积优化，转移时直接覆盖更新，允许重复累加。如果是求最小值（如硬币个数），需小心初始化为无效大值（如 a m o u n t + 1 amount + 1 amount+1），避免溢出或无效覆盖。

四、 二维 DP：网格与双序列

二维动态规划的状态通常由两个变量 (i, j) 决定，状态转移方程往往涉及 dp[i-1][j]（上方）、dp[i][j-1]（左方）以及 dp[i-1][j-1]（左上方/对角线状态）。

二维 DP 主要考察两类模型：

1. 网格图模型（Grid）：在一个矩阵上移动，求路径数或最小路径和。重点在于边界初始化。
2. 双序列模型（Sequence）：比较两个字符串或数组，求最长公共子序列（LCS）、编辑距离等。重点在于状态 dp[i][j] 往往表示“第一个序列的前 i 个”与“第二个序列的前 j 个”的关系。

4.1 网格路径模型：不同路径

题目链接：LeetCode 62. Unique Paths

题目描述：一个机器人位于 m x n 网格的左上角。机器人每次只能 向下 或者 向右 移动一步。试图达到网格的右下角。问总共有多少条不同的路径？

逻辑解析：

1. 状态定义：
   d p [ i ] [ j ] dp[i][j] dp[i][j] 表示从起点 ( 0 , 0 ) (0, 0) (0,0) 走到坐标 ( i , j ) (i, j) (i,j) 的路径总数。
2. 转移方程（加法原理）：
   机器人只能通过“向下”或“向右”到达 ( i , j ) (i, j) (i,j)。
   • 如果是“向下”走一步到达，说明上一步在 ( i − 1 , j ) (i-1, j) (i−1,j)。
   • 如果是“向右”走一步到达，说明上一步在 ( i , j − 1 ) (i, j-1) (i,j−1)。
   • 因此： d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j] = dp[i-1][j] + dp[i][j-1] dp[i][j]=dp[i−1][j]+dp[i][j−1]。
3. 初始化（边界陷阱）：
   网格类 DP 最容易出错的地方在于第一行和第一列。
   • 第一行：只能一直向右走，无法从上面下来，路径固定。因此第一行所有格子的路径数都是 1。
   • 第一列：只能一直向下走，无法从左边过来，路径固定。因此第一列所有格子的路径数都是 1。

Java 代码：

publicintuniquePaths(int m,int n){// 定义二维 DP 数组int[][] dp =newint[m][n];// 初始化// 第一列全为 1for(int i =0; i < m; i++){ dp[i][0]=1;}// 第一行全为 1for(int j =0; j < n; j++){ dp[0][j]=1;}// 填充中间网格// 从 (1, 1) 开始，因为 (0, x) 和 (x, 0) 已经初始化for(int i =1; i < m; i++){for(int j =1; j < n; j++){// 核心方程：来自上方 + 来自左方 dp[i][j]= dp[i -1][j]+ dp[i][j -1];}}// 返回右下角的结果return dp[m -1][n -1];}

空间优化（滚动数组原理）：
在计算 dp[i][j] 时，只需要“上一行”的数据和“当前行左边”的数据。因此，可以将二维压缩为一维（只保留一行的空间，通过“滚动更新”模拟多行计算，复用数组空间以降低复杂度到 O ( n ) O(n) O(n)）。
设 dp[j] 为当前行第 j 列的值。

• 更新前，dp[j] 存储的是上一行的值（等价于 dp[i-1][j]）。
• 更新时，dp[j-1] 存储的是当前行刚刚更新过的左边的值（等价于 dp[i][j-1]）。
• 方程变为：dp[j] = dp[j] (旧) + dp[j-1] (新)。

publicintuniquePaths(int m,int n){int[] dp =newint[n];// 初始化第一行，全为 1Arrays.fill(dp,1);// 从第二行开始遍历for(int i =1; i < m; i++){for(int j =1; j < n; j++){// dp[j] (新值) = dp[j] (上一行的旧值) + dp[j-1] (当前行左边的新值) dp[j]+= dp[j -1];}}return dp[n -1];}

4.2 双序列模型：最长公共子序列

这是二维 DP 中最经典、最具代表性的题目。理解了它，就理解了编辑距离、回文子序列等一系列困难题目。

题目链接：LeetCode 1143. Longest Common Subsequence

题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
子序列：不要求连续，但要求相对顺序一致。

逻辑解析：

1. 状态定义：
   定义 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 text1 的前 i i i 个字符（即 text1[0...i-1]）与 text2 的前 j j j 个字符（即 text2[0...j-1]）的最长公共子序列长度。
   • 为什么要用“前 i 个”而不是“索引 i”？
   • 为了方便处理空字符串的情况。 d p [ 0 ] [ 0 ] dp[0][0] dp[0][0] 表示两个空串的 LCS，长度为 0。这样可以避免复杂的下标越界判断。
2. 状态转移：
   考察 text1 的第 i i i 个字符（索引 i − 1 i-1 i−1）和 text2 的第 j j j 个字符（索引 j − 1 j-1 j−1）：
   • 情况 A：字符相等 (c1 == c2)
     既然这两个字符一样，那它们一定属于 LCS（最长公共子序列） 的一部分。
     LCS 长度 = 去掉这两个字符后的 LCS 长度 + 1。
     d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 dp[i][j] = dp[i-1][j-1] + 1 dp[i][j]=dp[i−1][j−1]+1。
   • 情况 B：字符不等 (c1 != c2)
     这两个字符不可能同时出现在 LCS 的末尾。LCS 要么继承自“text1 少一个字符”的结果，要么继承自“text2 少一个字符”的结果。取最大值。
     d p [ i ] [ j ] = max ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) dp[i][j]=max(dp[i−1][j],dp[i][j−1])。
3. 表格填充方向：
   由于 d p [ i ] [ j ] dp[i][j] dp[i][j] 依赖于左上 ( i − 1 , j − 1 ) (i-1, j-1) (i−1,j−1)、上 ( i − 1 , j ) (i-1, j) (i−1,j)、左 ( i , j − 1 ) (i, j-1) (i,j−1)，因此从左到右、从上到下遍历即可。

Java 代码：

publicintlongestCommonSubsequence(String text1,String text2){int m = text1.length();int n = text2.length();// dp[i][j] 对应 text1[0...i-1] 和 text2[0...j-1]// 大小设为 (m+1) x (n+1) 处理空串边界int[][] dp =newint[m +1][n +1];// i 和 j 从 1 开始，代表“第 1 个字符”for(int i =1; i <= m; i++){// 获取 text1 的字符，注意索引要 -1char c1 = text1.charAt(i -1);for(int j =1; j <= n; j++){char c2 = text2.charAt(j -1);if(c1 == c2){// 字符匹配：继承左上方状态 + 1 dp[i][j]= dp[i -1][j -1]+1;}else{// 字符不匹配：继承左方或上方的最大值// 意味着丢弃 c1 或者丢弃 c2，看谁剩下的 LCS 更长 dp[i][j]=Math.max(dp[i -1][j], dp[i][j -1]);}}}return dp[m][n];}

4.3 总结：网格模型 vs 双序列模型

网格路径 和 双序列匹配 两者的核心差异在于 状态定义的维度含义 以及 转移方程的触发条件。

• 物理含义与状态定义：
  • 网格模型：状态 ( i , j ) (i, j) (i,j) 对应几何坐标。 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示到达该坐标点的路径数或最小代价。通常直接在 m × n m \times n m×n 的数组上操作。
  • 双序列模型：状态 ( i , j ) (i, j) (i,j) 对应两个序列的前缀长度。 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示“序列 A 的前 i i i 个字符”与“序列 B 的前 j j j 个字符”的处理结果。为了处理空串情况，数组通常声明为 ( m + 1 ) × ( n + 1 ) (m+1) \times (n+1) (m+1)×(n+1)。
• 转移逻辑与依赖方向：
  • 网格模型：转移通常是无条件的，直接依赖于 上方 ( i − 1 , j ) (i-1, j) (i−1,j) 和 左方 ( i , j − 1 ) (i, j-1) (i,j−1) 的累加或最值。
  • 双序列模型：转移是有条件的，依赖于当前字符是否匹配 (s1[i-1] == s2[j-1])。
    • 匹配时：通常继承 左上方 ( i − 1 , j − 1 ) (i-1, j-1) (i−1,j−1) 的状态（如 LCS +1）。
    • 不匹配时：通常继承 上方 或 左方 的最值（如 LCS 取 max）。
• 初始化：
  • 网格模型：第一行和第一列通常初始化为 1（代表只有一条直路）或累加值。
  • 双序列模型：第 0 行和第 0 列代表“空串”参与运算。对于 LCS 问题初始化为 0；对于编辑距离问题，初始化为索引值 i i i 或 j j j（代表删除/插入操作数）。

五、 总结与最佳实践

动态规划是算法中区分度较高的板块，其本质是将最优子结构与重叠子问题结合，通过填表法将指数级暴力搜索优化为多项式级迭代。掌握 DP 在于能够根据题意快速构建状态转移方程。

5.1 DP 解题的四步

在面对 DP 问题时，通常可以通过以下流程分析问题：

1. 定义状态：
   明确 d p dp dp 数组下标的物理含义。
   • 线性问题： d p [ i ] dp[i] dp[i] 通常表示“前 i i i 个元素”或“以第 i i i 个元素结尾”的最优解。
   • 背包问题： d p [ i ] [ j ] dp[i][j] dp[i][j] 表示“前 i i i 个物品在容量 j j j 下”的最优解（优化后为 d p [ j ] dp[j] dp[j]）。
   • 双序列问题： d p [ i ] [ j ] dp[i][j] dp[i][j] 表示“序列 A 的前 i i i 个”与“序列 B 的前 j j j 个”的匹配结果。
2. 推导方程：
   思考“当前状态”是如何由“之前的状态”推导出来的。
   • 最后一步法：假设已经完成了前 i − 1 i-1 i−1 步，第 i i i 步有哪些选择（选/不选、替换/删除）？
   • 操作映射：将题目中的操作（如“爬一步”、“偷这间”、“放入背包”）转化为数学运算（+1, max, min）。
3. 初始化：
   处理边界条件，防止数组越界。
   • 逻辑边界： d p [ 0 ] dp[0] dp[0] 或 d p [ 1 ] dp[1] dp[1] 的物理意义是什么？（如爬楼梯 d p [ 1 ] = 1 dp[1]=1 dp[1]=1）。
   • 计算边界：求最小值时初始化为无穷大（如零钱兑换），求最大值时初始化为 0 或负无穷。
4. 确定遍历顺序：
   • 普通 DP：通常从左到右，从小到大。
   • 0/1 背包（一维优化）：内层循环必须从大到小（防止重复使用物品）。
   • 完全背包（一维优化）：内层循环必须从小到大（允许重复使用物品）。

5.2 复杂度分析

• 时间复杂度： O ( 状态数量 × 单次转移耗时 ) O(\text{状态数量} \times \text{单次转移耗时}) O(状态数量×单次转移耗时)。
  • 线性 DP： O ( N ) O(N) O(N)。
  • 背包/双序列/网格 DP： O ( N × M ) O(N \times M) O(N×M)。
• 空间复杂度：
  • 基础解法：与状态表大小一致（ O ( N ) O(N) O(N) 或 O ( N 2 ) O(N^2) O(N2)）。
  • 滚动数组优化：如果状态 d p [ i ] dp[i] dp[i] 只依赖于 d p [ i − 1 ] dp[i-1] dp[i−1]（或 d p [ i ] [ j ] dp[i][j] dp[i][j] 只依赖上一行），可以将空间维数降低一维（例如 O ( N 2 ) → O ( N ) O(N^2) \rightarrow O(N) O(N2)→O(N)）。

5.3 常见误区

1. 数组越界：
   DP 代码最常见的 Bug 是 dp[i-1]、dp[i-2] 或 dp[j-coin] 越界。
   • 对策：根据转移方程需要的 offset（偏移量），设定循环的起始点（如从 i=2 开始），或者在循环内加 if (i >= coin) 判断。
2. 状态定义的偏差：
   “第 i 个” vs “索引 i” 的坑。
   • 建议：涉及“前 i 个”或双序列问题时，数组开 n + 1，下标 1 代表第 1 个元素，下标 0 代表空集/空串，这样能极大简化边界判断。