目录前言一、打家劫舍LeetCode 198题目描述核心思路一维 DP 的状态转移状态定义转移方程边界条件代码实现Java 版关键知识点二、完全平方数LeetCode 279题目描述核心思路完全背包 DP状态定义转移方程边界条件代码实现Java 版关键知识点前言动态规划DP的进阶阶段两道经典中等题是绕不开的一道是「打家劫舍」考验一维 DP 的状态转移与边界处理另一道是「完全平方数」结合了 BFS 和完全背包的思想能帮你打开 DP 的解题视野。本文从题目分析、状态定义、转移方程、代码实现一步步讲透帮你掌握这类题的通用解题模板。一、打家劫舍LeetCode 198题目描述你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。核心思路一维 DP 的状态转移这道题的核心矛盾是不能同时偷相邻的房子因此对于第i间房我们有两种选择偷第i间房那么第i-1间房一定不能偷总金额 dp[i-2] nums[i]不偷第i间房那么最高金额就是偷前i-1间房的最高金额即dp[i-1]状态定义dp[i]表示偷前i间房能获得的最高金额。转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])边界条件dp[0] nums[0]只有一间房直接偷dp[1] max(nums[0], nums[1])两间房偷金额高的那间代码实现Java 版java运行public class HouseRobber { // 基础版数组存储 public int rob(int[] nums) { if (nums null || nums.length 0) return 0; if (nums.length 1) return nums[0]; int[] dp new int[nums.length]; dp[0] nums[0]; dp[1] Math.max(nums[0], nums[1]); for (int i 2; i nums.length; i) { dp[i] Math.max(dp[i-1], dp[i-2] nums[i]); } return dp[nums.length - 1]; } // 优化版滚动变量空间O(1) public int robOptimized(int[] nums) { if (nums null || nums.length 0) return 0; if (nums.length 1) return nums[0]; int prevPrev nums[0]; int prev Math.max(nums[0], nums[1]); for (int i 2; i nums.length; i) { int curr Math.max(prev, prevPrev nums[i]); prevPrev prev; prev curr; } return prev; } public static void main(String[] args) { HouseRobber solution new HouseRobber(); int[] nums {1,2,3,1}; System.out.println(solution.rob(nums)); // 输出4偷13 System.out.println(solution.robOptimized(nums)); // 输出4 } }关键知识点时间复杂度O (n)仅遍历一次数组空间复杂度O (n)可优化到 O (1)只保留前两个状态面试拓展后续变种题「打家劫舍 II环形房屋」「打家劫舍 III二叉树结构」核心思路都是状态转移的变种。二、完全平方数LeetCode 279题目描述给你一个整数n返回和为n的完全平方数的最少数量。完全平方数是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9和16都是完全平方数而3和11不是。核心思路完全背包 DP这道题本质是完全背包问题背包容量n物品所有小于等于n的完全平方数如1,4,9,16...目标用最少的物品平方数装满背包状态定义dp[i]表示和为i的完全平方数的最少数量。转移方程对于每个i遍历所有小于等于i的完全平方数j*j则dp[i] min(dp[i - j*j] 1)边界条件dp[0] 0和为 0 时需要 0 个平方数其余dp[i]初始化为无穷大后续更新最小值。代码实现Java 版java运行public class PerfectSquares { public int numSquares(int n) { int[] dp new int[n 1]; // 初始化设置为无穷大 for (int i 1; i n; i) { dp[i] Integer.MAX_VALUE; } dp[0] 0; // 边界条件 // 遍历所有数 for (int i 1; i n; i) { // 遍历所有小于等于i的完全平方数 for (int j 1; j * j i; j) { dp[i] Math.min(dp[i], dp[i - j*j] 1); } } return dp[n]; } // BFS 解法拓展思路 public int numSquaresBFS(int n) { QueueInteger queue new LinkedList(); SetInteger visited new HashSet(); queue.offer(0); visited.add(0); int level 0; while (!queue.isEmpty()) { int size queue.size(); level; for (int i 0; i size; i) { int curr queue.poll(); // 尝试加上所有完全平方数 for (int j 1; j * j n; j) { int next curr j*j; if (next n) return level; if (next n !visited.contains(next)) { visited.add(next); queue.offer(next); } } } } return -1; } public static void main(String[] args) { PerfectSquares solution new PerfectSquares(); System.out.println(solution.numSquares(12)); // 输出3444 System.out.println(solution.numSquaresBFS(12)); // 输出3 } }关键知识点时间复杂度O (n√n)外层遍历 n内层遍历√n 个平方数空间复杂度O (n)存储 DP 数组拓展思路BFS 解法按层遍历第一次到达 n 时的层数就是最少数量更直观但空间复杂度更高。