今天的练习并不是学习新的 DP 模板，而是围绕两个最经典的模型：打家劫舍 与 爬楼梯，去做“变形题”的识别与迁移。
通过这一组题目的训练，我逐渐体会到：
动态规划的关键不在于记公式，而在于识别“本质模型”，并主动把陌生题目转化为熟悉结构。
基础题目：198. 打家劫舍
打家劫舍模型变形
- 740. 删除并获得点数
爬楼梯模型变形（方案数）
- 2466. 统计构造好字符串的方案数
- 377. 组合总和 Ⅳ
- 2266. 统计打字方案数
经典二维 DP
- 64. 最小路径和
核心模型回顾
在进入具体题目之前，先明确两个核心模型的“本质约束”。
1. 打家劫舍模型的本质
- 每个元素都有「选 / 不选」两种状态
- 一旦选择某个元素，就会限制相邻元素不能被选择
- 状态转移通常是：
1 | dp[i] = max(dp[i - 1], dp[i - 2] + value[i]) |
重点不在“房子”，而在相邻约束
2. 爬楼梯模型的本质
- 本质是一个排列问题
- 顺序不同 = 不同方案
- 给定一个目标值
target - 每一步可以选择若干“步长”，问总方案数
只要是：
- 「目标值固定」
- 「每一步可以选择若干选项」
- 「顺序敏感」
都可以往爬楼梯模型上靠
结合具体题目分析
740. 删除并获得点数 —— 打家劫舍的值域改造
题意简述：
选择一个数 nums[i]，可以获得 nums[i] 的点数，但会删除所有值为 nums[i] - 1 和 nums[i] + 1 的元素。
思路转化
这道题的难点在于：
- 原数组中，相同数字可能出现多次
- 删除的是“值相邻”，而不是“位置相邻”
关键一步：构造打家劫舍的条件
将数组转为值域数组
sums[x]：表示值为x的所有元素之和- 例如：
1 | nums = [2,2,3,3,3,4] |
此时问题变成：
在
sums数组中，选择若干不相邻的元素，使得总和最大
完全等价于打家劫舍
2466. 统计构造好字符串的方案数 —— 爬楼梯模型
这道题表面是字符串问题，但本质非常清晰：
- 当前字符串长度 = 已爬的台阶数
- 每一步可以：
- 增加
zero个字符 - 或增加
one个字符
- 增加
- 问：长度在
[low, high]区间内的方案总数
这是标准的爬楼梯模型
dp[i]：构造长度为i的方案数- 每次从
i - zero或i - one转移而来
377. 组合总和 Ⅳ —— 爬楼梯 + 顺序敏感
这道题非常具有代表性：
- 给定
nums - 目标和
target - 不同顺序算不同方案
本质理解
可以这样理解：
爬
target阶楼梯
每次可以爬nums[i]阶
问一共有多少种爬法
顺序不同 → 不同路径
2266. 统计打字方案数 —— 分组 + 爬楼梯
这道题本身规则较复杂，但从 DP 角度可以拆解为：
- 按连续相同数字分组
- 每一组内部：
- 是一个「爬楼梯问题」
- 不同按键允许的最大步长不同
- 最终答案 = 各组方案数相乘
这是一个非常典型的：
局部 DP + 全局组合
64. 最小路径和 —— 经典二维 DP
这是标准的网格 DP：
dp[i][j]表示到(i, j)的最小路径和- 当前状态只依赖：
- 上方
(i - 1, j) - 左方
(i, j - 1)
- 上方
1 | dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] |
没有变形，但非常适合作为 DP 基础模板反复巩固
心得与方法论总结
1. 打家劫舍 ≠ 偷房子
打家劫舍的真正核心是：
选择一个元素，会导致“相邻状态失效”
- 740 题中，相邻的是「值」
- 所以我们主动构造值域数组，人为制造相邻关系
没有条件，就创造条件
2. 爬楼梯 = 顺序敏感的方案计数
爬楼梯模型特别适合解决：
- 方案数问题
- 和 / 长度固定的问题
- 顺序不同算不同的情况
例如：
- 字符串构造
- 数字组合
- 步数累加
把「目标值」当成台阶数，把「选择」当成一步能走的距离
总结
通过今天这一组题目的训练，我对动态规划有了一个更重要的认知转变：
DP 的关键不是记住状态转移方程，而是识别题目的“原型模型”。
- 看到「相邻不能同时选」 → 想打家劫舍
- 看到「目标固定 + 多种选择 + 顺序敏感」 → 想爬楼梯
相关代码
本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。