DP笔记(3)：单线DP之爬楼梯、打家劫舍、解码方法
Author：zhoulujun Date：
单线行动态规划，还是从最基础的题目开始讲
爬楼梯合集
爬楼梯
这道题目算得上最简单的动态规划类的题目了
爬楼梯解法
步骤一：定义子问题
我们来一个一个分析一下：
当只有 1 阶台阶时，你只有一种方式爬到顶端
当只有 2 阶台阶时，你有两种方式，如示例1所示
当只有 3 阶台阶时，你有三种方式，如示例2所示
分析到这里的时候，看看这几个数据，我有一个大胆的猜测，当只有 4 阶台阶时，可以有 爬到第2阶台阶所需要的方法数 加上 爬到第3阶台阶所需要的方法数 种方法数，为什么这么说呢？你想想，要想爬到第4阶台阶，你只能是从第3阶或者第2阶台阶爬上来的，只有这两种方式对吧，所以：
4阶方法总数 = 3阶方法总数 + 2阶方法总数 ……
再看是否存在 存在重复子问题，其实爬楼梯和斐波那契数列类似，最终的状态转移方程是一样的，所以显然存在重复子问题。当然直观来看也容易分析出，10 阶台阶的爬法包含了 8、9 阶的爬法，而 9 阶台阶爬法包含了 8 阶的，所以存在重复子问题。
定义子问题：
我们可以将到达第 n 阶台阶的方法看作一个子问题，记为 f(n)。显然，到达第 1 阶台阶的方法只有一种，就是从第 0 阶台阶走 1 阶台阶，即 f(1) = 1。到达第 2 阶台阶的方法有两种，可以从第 1 阶台阶走 1 阶台阶，也可以从第 0 阶台阶直接走 2 阶台阶，即 f(2) = f(1) + f(0) = 2。
步骤二：写出子问题的递推关系
根据上述分析，我们可以得出以下递推关系：f(n) = f(n-1) + f(n-2)
步骤三：确定 DP 数组的计算顺序
根据递推关系，我们可以从下往上计算 DP 数组，即先计算 f(1) 和 f(2)，再计算 f(3)、f(4)，以此类推。
所以爬楼梯的状态转移方程为：
dp(i) = dp(i-1) + dp(i-2)
dp(1) = 1
dp(2) = 2
步骤四：空间优化（可选）
由于递推关系只涉及到前两个子问题的解，因此我们可以使用两个变量来存储前两个子问题的解，从而避免使用 DP 数组。具体来说，我们可以定义两个变量 pre 和 cur，分别表示到达第 n-1 阶台阶的方法数和到达第 n 阶台阶的方法数。初始状态为 pre = 1，cur = 2。然后，我们可以迭代计算 cur 的值，每次迭代将 cur 的值赋给 pre，并重新计算 cur 的值。
爬楼梯代码实现
字问题递归表述
function dp(i) {
switch (i) {
case 1:
return 1;
case 2:
return 2;
default:
return dp(i - 1) + dp(i - 2);
}
}这样写重复计算了子结构，所以我们不要每次傻傻的执行 dp(i - 1)（因为这样计算了超多重复子问题），我们需要用缓存兜底：
递归改为迭代
function climbStairs(n) {
if (n <= 1) return 1;
let dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}空间优化
function climbStairs(n) {
if (n <= 1) return 1;
let prev1 = 1, prev2 = 1; // 用两个变量来存储前两个状态
for (let i = 2; i <= n; i++) {// 迭代计算每一级的方法数
let curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;// 返回最后的状态
}使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：输入：cost = [10,15,20] 输出：15
解释：你将从下标为 1 的台阶开始。- 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。
使用最小花费爬楼梯解法
这里忽略详细的推导过程
问题分析
到达第i级台阶的阶梯顶部的最小花费，有两个选择：
先付出最小总花费minCost[i-1]到达第i级台阶（即第i-1级台阶的阶梯顶部），踏上第i级台阶需要再花费cost[i]，再迈一步到达第i级台阶的阶梯顶部，最小总花费为minCost[i-1] + cost[i])；
先付出最小总花费minCost[i-2]到达第i-1级台阶（即第i-2级台阶的阶梯顶部），踏上第i-1级台阶需要再花费cost[i-1]，再迈两步跨过第i级台阶直接到达第i级台阶的阶梯顶部，最小总花费为minCost[i-2] + cost[i-1])；
则minCost[i]是上面这两个最小总花费中的最小值。
minCost[i] = min(minCost[i-1] + cost[i], minCost[i-2] + cost[i-1])。
最小总花费的初始值为：
第0级台阶： minCost[0] = min(cost[-1], cost[0]) = min(0, cost[0]) = 0，
第1级台阶： minCost[1] = min(cost[0], cost[1])。
第i级台阶： minCost[i] = min(minCost[i-1] + cost[i], minCost[i-2] + cost[i-1])。
步骤二：写出子问题的递推关系
为了爬到第 n 级台阶，你可以从第 n-1 级或者第 n-2 级台阶跨一步或两步上来，因此：
f(n)=min(f(n−1)+cost[n−1],f(n−2)+cost[n−2])
步骤三：确定 DP 数组的计算顺序
我们使用动态规划数组来解决这个问题。从底向上计算，避免重复计算子问题。
确定边界条件：
f(0) = 0：因为你可以从地面开始爬，不需要任何费用。
f(1) = 0：类似地，第一步可以是从地面直接跨到第一级，不需要任何费用。
递推计算：
对于 n >= 2，按照递推公式 f(n) = min(f(n-1) + cost[n-1], f(n-2) + cost[n-2]) 进行计算。
使用最小花费爬楼梯代码
使用 DP 数组的实现
function minCostClimbingStairs(cost) {
const n = cost.length;
if (n === 0) return 0;
if (n === 1) return cost[0];
let dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 0;
for (let i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}空间优化后的实现
我们注意到每次计算 f(n) 只需要 f(n-1) 和 f(n-2)，因此可以用两个变量代替整个数组，从而优化空间复杂度到 O(1)。
function minCostClimbingStairs(cost) {
const n = cost.length;
if (n === 0) return 0;
if (n === 1) return cost[0];
let prev1 = 0;
let prev2 = 0;
for (let i = 2; i <= n; i++) {
let curr = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}打家劫舍合集
打家劫舍共4道题，1,2,4 题难度依次变大，3题为树结构。
打家劫舍 I：小偷想在一条街道上排成一列的房屋中进行偷窃，但相邻房屋的警报系统会相互触发，因此他不能连续抢劫两间房屋。请问小偷最多能偷取多少钱？
打家劫舍 II：与第一题不同的是，这道题中房屋可以环形排列。请问小偷最多能偷取多少钱？
打家劫舍 III：这道题中，房屋除了可以排成一列之外，还可以形成一棵树形结构。请问小偷最多能偷取多少钱？
打家劫舍 IV：这道题中，房屋可以排成一列，也可以形成一棵树形结构。与第三题不同的是，每个房屋中除了有金钱之外，还有一些物品，小偷可以选择偷取金钱，也可以选择偷取物品，但不能同时偷取两者。请问小偷最多能获得多少价值？
第一道是比较标准的动态规划问题，而第二道融入了环形数组的条件，第三道更绝，把动态规划的自底向上和自顶向下解法和二叉树结合起来，我认为很有启发性。 1-3题只是房屋的排列方式不同，都只能偷取金钱，第4题可以偷取金钱或物品。
每道题目的限制条件有所不同，1 是相邻的不能同时抢，2 是环形结构的相邻不能同时抢，3是树形结构的父子节点不能同时抢，4 是需要选择 k 个房屋进行抢劫。
四题考察的重点都是动态规划的思想和方法。但具体的实现方法和需要考虑的问题不同，2 需要处理环形数组问题，3需要进行树的遍历，4 则结合了二分查找和前缀和等方法。
打家劫舍I
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
打家劫舍I动态五部曲分析
步骤一：定义子问题
f(k)表示从前面k个房子能获取的最大金额；
原问题要能由子问题表示。例如这道小偷问题中，k=n 时实际上就是原问题；
一个子问题的解要能通过其他子问题的解求出。例如本题：f(k) 可以由 f(k-1)和 f(k-2)求出，具体原理后面会解释。这个性质就是所说的"最优子结构"。如果定义不出这样的子问题，那么这道题实际上没法用动态规划解。
步骤二：写出子问题的递推关系
每个房子的金额用H表示，那么k个房子有两种偷发，如上图所示。容易得出递推公式（重要）：
注意这里涉及到边界值：
k=0时，f(0)=0
k=1时，f(1)=H0
步骤三：确定 DP 数组的计算顺序
那么，既然 DP 数组中的依赖关系都是向右指的，DP 数组的计算顺序就是从左向右。这样我们可以保证，计算一个子问题的时候，它所依赖的那些子问题已经计算出来了。
确定了 DP 数组的计算顺序之后，我们就可以写出题解代码了：见3.3的代码一。
步骤四：空间优化（可选）
最后一步计算 f(n) 的时候，实际上只用到了 f(n-1)和 f(n-2) 的结果。那么只用两个变量保存两个子问题的结果，就可以依次计算出所有的子问题。下面的图比较了空间优化前和优化后的对比关系，代码见3.3代码二：
打家劫舍I代码
对于连续的 n 栋房子：H1 ,H2 ,H3 ......Hn ，小偷挑选要偷的房子，且不能偷相邻的两栋房子，方案无非两种：
方案一：挑选的房子中包含最后一栋；
方案二：挑选的房子中不包含最后一栋；
获得的最大收益的最终方案，一定在这两种方案中产生，用代码表述就是：
最优结果 = Math.max(方案一最优结果，方案二最优结果)
子问题的递归表述
var robTo = function (nums, lastIndex) {
if (lastIndex === 0) return nums[0];
// 方案一，包含最后一栋房子，则应该丢弃倒数第二栋房子
let sum1 = robTo(nums, lastIndex - 2) + nums[lastIndex];
// 方案二，不包含最后一栋房子，那么方案二的结果就是到偷到 lastIndex-1 为止的最优结果
let sum2 = robTo(nums, lastIndex - 1);
return Math.max(sum1, sum2);
};将问题表述成最优子问题的解后，这个问题就解决了：
var rob = function(nums) {
return robTo(nums, nums.length - 1);
};递归转迭代
到上一步为止，该问题就已经解决了。但是递归的方式性能太差，中间有太多重复的计算，所以还需要最后一步：将 自顶向下 的递归，转化成 自底向上 的迭代。
var rob = function(nums) {
const len = nums.length;
if(len == 0) return 0;
const dp = new Array(len + 1);
dp[0] = 0;
dp[1] = nums[0];
for(let i = 2; i <= len; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
}
return dp[len];
};空间优化
使用两个变量取代数组。
var rob = function(nums) {
if (nums.length === 0) {
return 0;
}
if (nums.length === 1) {
return nums[0];
}
// 仍然用两个变量来存储方案一和方案二的最优结果
// 不同的是，这次从0开始，lastIndex 取最小值 1
let sum1 = nums[0];
let sum2 = nums[1];
// 然后通过迭代不断增大 lastIndex，过程中维护新的sum1，sum2，直到数组末尾
for (let lastIndex=2; lastIndex<nums.length; lastIndex++) {
let tmp = sum1;
// 此时的方案一就是上一步中的方案二，
// 但要求的是最优解，所以要判断前一步的 sum1 和 sum2 哪个更大
if (sum2 > sum1) {
sum1 = sum2;
}
// sum2 是包含最后一栋房子的方案，
// 每向后增加一栋房子，就是前一步的 sum1（不包含 lastIndex - 1 ）
// 加上当前 lastIndex 栋房子的金钱
sum2 = tmp + nums[lastIndex];
}
return sum1 > sum2 ? sum1 : sum2;
};打家劫舍 II代码
这道题目和198.打家劫舍 (opens new window)是差不多的，唯一区别就是成环了。
对于一个数组，成环的话主要有如下三种情况：
情况一：考虑不包含首尾元素
情况二：考虑包含首元素，不包含尾元素
情况三：考虑包含尾元素，不包含首元素
注意我这里用的是"考虑"，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！ 对于情况三，取nums[1] 和 nums[3]就是最大的。
而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。
分析到这里，本题其实比较简单了。 剩下的和198.打家劫舍 (opens new window)就是一样的了。
var rob = function (nums) {
const len = nums.length;
if (len == 0) return 0;
if (len == 1) return nums[0];
const result1 = robRange(nums, 0, len - 2);
const result2 = robRange(nums, 1, len - 1);
return Math.max(result1, result2);
};
function robRange(nums, start, end) {
if (end === start) return nums[start];
const n = end + 1;
const dp = new Array(n);
dp[start] = 0;
dp[start + 1] = nums[start];
for (let i = start + 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[n];
}这个代码是为了保持和打家劫舍1 保持一致。也可以这样写：https://programmercarl.com/0213.打家劫舍II.html
打家劫舍3与4，因为涉及到树形结构，而本篇主要是讲单行线动态规划，所以先放一放。
解码方法合集
其实就是用字母去编码数字，但是不是26进制，因为单个字符可以被映射为'A'到'Z'的字母（1到26），给定的字符串可能有多种解码方式。
解码方法
一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：'A' -> "1" 'B' -> "2" ... 'Z' -> "26"
要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为： "AAJF" 对应分组 (1 1 10 6) 、 "KJF" 对应分组 (11 10 6)
注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
示例 1： 输入：s = "12" 输出：2 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2： 输入：s = "226" 输出：3 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
这也是一道典型的动态规划题目，和爬楼梯问题有异曲同工之妙。我们来思考：
对于一个数字来说[1,9]这九个数字能够被识别为一种编码方式
对于两个数字来说[10, 26]这几个数字能被识别为一种编码方式
我们考虑用 dp[i]来切分子问题， 那么 dp[i]表示的意思是当前字符串的以索引 i 结尾的子问题。这样的话，我们最后只需要取 dp[s.length] 就可以解决问题了。
定义状态
定义状态 dp[i] 表示为：字符串 s 前 i 个字符构成的字符串可能构成的翻译方案数。
定义子问题的递推关系
s[i - 1]的编码范围是1-9，此时不会产生新的编码方法，状态转移方程：dp[i] = dp[i - 1];。
s[i - 2] + s[i - 1]的范围是10~26，dp[i]与dp[i - 1]和dp[i - 2]有关，而dp[i - 1]在步骤 1 已经计算过，因此该条件的状态转移方程：dp[i] += dp[i - 2];。
如果在判断过10和20后，如果s[i - 1]还有出现0，表示当前一定出现了30、40、50等无法解码的情况，可以直接返回 0。
状态转移方程
dp[i] 的来源有两种情况：
使用了一个字符，对 s[i] 进行翻译。只要 s[i]!=0，就可以被翻译为 A ~ I 的某个字母，此时方案数为 dp[i]=dp[i−1]。
使用了两个字符，对s[i−1] 和s[i] 进行翻译，只有 s[i−1]!=0，且s[i−1] 和 s[i] 组成的整数必须小于等于 2626 才能翻译，可以翻译为 J ~ Z 中的某字母，此时方案数为 dp[i]=dp[i−2]。
这两种情况有可能是同时存在的，也有可能都不存在。在进行转移的时候，将符合要求的方案数累加起来即可。
状态转移方程可以写为：
初始数组
字符串为空时，只有一个翻译方案，翻译为空字符串，即 dp[0]=1。
字符串只有一个字符时，需要考虑该字符是否为 0，不为 0 的话，dp[1]=1，为 0 的话，dp[0]=0。
最终代码
var numDecodings = function (s) {
// 创建一个s.length + 1长度的数组递推，索引从1到s.length，对应s的每个位置
// dp[i]对应的字符串位置为s[i - 1]
let dp = new Array(s.length + 1).fill(0);
// 由于dp[i]的状态与dp[i - 1]和dp[i - 2]有关，而我们只能创建s[0]的初始状态
// 0位置设置为1，保证递推能有效进行。
dp[0] = 1;
// 创建s[0]的初始状态，为0时解码方法为0
dp[1] = s[0] === '0' ? 0 : 1;
// 从s[1]开始递推
for (let i = 2; i < dp.length; i++) {
let one = s[i - 1]; // 当前位置的编码
let two = s[i - 2] + s[i - 1]; // 连续两位的编码
// 如果当前位置编码为0-9，表示没有新增方法，方法数与dp[i - 1]相同
if (one >= '1' && one <= '9') {
dp[i] = dp[i - 1];
}
// 如果前两位编码为10-26，表示还需要考虑dp[i - 2]的编码方法，将其累加到dp[i]
// 而dp[i - 1]已经累加过了，无需重复计算
if (two >= '10' && two <= '26') {
dp[i] += dp[i - 2];
} else if (one === '0') {
// 当前编码为0，无法解码，返回0
// 10和20的编码已经处理过，此处不会包含这两个场景
return 0;
}
}
return dp[s.length];// 递推到数组最后位置，表示找到了解码方法数量
};解码方法 II
……………………
除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。
给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。
示例 1：输入：s = "*" 输出：9
解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。因此，"*" 总共有 9 种解码方法。
示例 2： 输入：s = "1*" 输出：18
解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。因此，"1*" 共有 9 * 2 = 18 种解码方法。
decode-ways-ii扩展了decode-ways的解法，允许使用字符'*'来表示1到9的任意数字。
由于'*'的存在，可能有多种解码方法，需要对这些情况进行详细的考虑和处理。
具体地可以看：
最终代码
var numDecodingsII = function(s) {
const MOD = 1000000007;
const n = s.length;
let dp = new Array(n + 1).fill(0);
dp[0] = 1; // 空字符串有一种解码方法
dp[1] = decodeSingle(s[0]); // 第一个字符的解码方法数
function decodeSingle(char) {
if (char === '0') return 0;
if (char === '*') return 9;
return 1;
}
function decodeDouble(char1, char2) {
if (char1 === '*' && char2 === '*') {
return 15; // 11-19, 21-26
} else if (char1 === '*') {
if (char2 >= '0' && char2 <= '6') return 2; // 1*, 2*
else return 1; // 3* - 9*
} else if (char2 === '*') {
if (char1 === '1') return 9; // 10-19
else if (char1 === '2') return 6; // 20-26
else return 0;
} else {
let num = parseInt(char1 + char2);
if (num >= 10 && num <= 26) return 1;
else return 0;
}
}
for (let i = 2; i <= n; i++) {
let oneDigit = s[i - 1];
let twoDigits = s[i - 2] + s[i - 1];
dp[i] += dp[i - 1] * decodeSingle(oneDigit);
dp[i] += dp[i - 2] * decodeDouble(s[i - 2], s[i - 1]);
dp[i] %= MOD;
}
return dp[n];
};参考文章：
第九章动态规划——使用最小花费爬楼梯 https://blog.csdn.net/DDDDWJDDDD/article/details/137244557
650.只有两个键的键盘（动态规划） https://blog.csdn.net/Linke66/article/details/120384747
Leetcode [650] 只有两个键的键盘 & Leetcode [651] 四键键盘 动态规划 https://www.cnblogs.com/zl1991/p/14742514.html
转载本站文章《DP笔记(3)：单线DP之爬楼梯、打家劫舍、解码方法》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9112.html