当前位置：首页 > news >正文

两道中等 DP 题拆解：打家劫舍完全平方数

news 2026/4/17 12:31:24

前言

一、打家劫舍（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（偷1+3） 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) { Queue<Integer> queue = new LinkedList<>(); Set<Integer> 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)); // 输出：3（4+4+4） System.out.println(solution.numSquaresBFS(12)); // 输出：3 } }