• home > theory > algorithm > leetcode >

    DP笔记(2):线性动态规划之单线性问题之爬楼梯/打家劫舍

    Author:zhoulujun Date:

    线性动态规划题目爬楼梯爬楼梯https: leetcode cn problems climbing-stairs description 使用最小花费爬楼梯https: leetcode cn problem

    线性动态规划简介

    线性动态规划:具有「线性」阶段划分的动态规划方法统称为线性动态规划(简称为「线性 DP」),如下图所示。

    线性 DP

    如果状态包含多个维度,但是每个维度上都是线性划分的阶段,也属于线性 DP。比如背包问题、区间 DP、数位 DP 等都属于线性 DP。

    线性 DP 问题的划分方法有多种方式。

    • 如果按照「状态的维度数」进行分类,我们可以将线性 DP 问题分为:

      • 一维线性 DP 问题

      • 二维线性 DP 问题

      • 多维线性 DP 问题

    • 如果按照「问题的输入格式」进行分类,我们可以将线性 DP 问题分为:

      • 单串线性 DP 问题

      • 双串线性 DP 问题

      • 矩阵线性 DP 问题

      • 无串线性 DP 问题

    本文中,我们将按照问题的输入格式进行分类,对线性 DP 问题中各种类型问题进行一一讲解。

    单串线性 DP 问题

    单串线性 DP 问题:问题的输入为单个数组或单个字符串的线性 DP 问题。状态一般可定义为dp[i],表示为:

    1. 「以数组中第i 个位置元素 nums[i] 为结尾的子数组(nums[0]...nums[i])」的相关解。

    2. 「以数组中第 i−1 个位置元素nums[i−1] 为结尾的子数组(nums[0]...nums[i−1])」的相关解。

    3. 「以数组中前 i 个元素为子数组(nums[0]...nums[i−1])」的相关解。

    这 33种状态的定义区别在于相差一个元素nums[i]。

    1. 第 1 种状态:子数组的长度为 i+1,子数组长度不可为空;

    2. 第 22种状态、第 3 种状态:这两种状态描述是相同的。子数组的长度为i,子数组长度可为空。在i=0 时,方便用于表示空数组(以数组中前 0 个元素为子数组)。

    双串线性 DP 问题

    双串线性 DP 问题:问题的输入为两个数组或两个字符串的线性 DP 问题。状态一般可定义为dp[i][j],表示为:

    1. 「以第一个数组中第i 个位置元素 nums1[i] 为结尾的子数组(nums1[0]...nums1[i])」与「以第二个数组中第 j 个位置元素 nums2[j] 为结尾的子数组(nums2[0]...nums2[j])」的相关解。

    2. 「以第一个数组中第 i−1 个位置元素 nums1[i−1] 为结尾的子数组(nums1[0]...nums1[i−1])」与「以第二个数组中第 j−1 个位置元素 nums2[j−1] 为结尾的子数组(nums2[0]...nums2[j−1])」的相关解。

    3. 「以第一个数组中前 i 个元素为子数组(nums1[0]...nums1[i−1])」与「以第二个数组中前 j 个元素为子数组(nums2[0]...nums2[j−1])」的相关解。

    这 33 种状态的定义区别在于相差一个元素 nums1[i] 或 nums2[j]。

    1. 第 11 种状态:子数组的长度为 i+1 或 j+1,子数组长度不可为空

    2. 第 22 种状态、第 33 种状态:子数组的长度为 i 或 j,子数组长度可为空。i=0 或j=0 时,方便用于表示空数组(以数组中前 00 个元素为子数组)。

    矩阵线性 DP问题

    矩阵线性 DP 问题:问题的输入为二维矩阵的线性 DP 问题。状态一般可定义为 dp[i][j],表示为:从「位置 (0,0)(0,0)」到达「位置 (i,j)」的相关解。

    无串线性 DP 问题

    无串线性 DP 问题:问题的输入不是显式的数组或字符串,但依然可分解为若干子问题的线性 DP 问题。


    线性动态规划题目

    爬楼梯合集

    爬楼梯

    这道题目算得上最简单的动态规划类的题目了

    爬楼梯解法

    步骤一:定义子问题

    我们来一个一个分析一下:

    • 当只有 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;// 返回最后的状态
    }


    使用最小花费爬楼梯

    使用最小花费爬楼梯解法

    这里忽略详细的推导过程

    问题分析

    到达第i级台阶的阶梯顶部的最小花费,有两个选择:

    1. 先付出最小总花费minCost[i-1]到达第i级台阶(即第i-1级台阶的阶梯顶部),踏上第i级台阶需要再花费cost[i],再迈一步到达第i级台阶的阶梯顶部,最小总花费为minCost[i-1] + cost[i]);

    2. 先付出最小总花费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 数组的计算顺序

    我们使用动态规划数组来解决这个问题。从底向上计算,避免重复计算子问题。

    1. 确定边界条件:

      • f(0) = 0:因为你可以从地面开始爬,不需要任何费用。

      • f(1) = 0:类似地,第一步可以是从地面直接跨到第一级,不需要任何费用。

    2. 递推计算:

      • 对于 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题为树结构。

    https://leetcode.cn/problems/house-robber/

    https://leetcode.cn/problems/house-robber-ii/description/

    https://leetcode.cn/problems/house-robber-iv/description/


    https://leetcode.cn/problems/house-robber-iii/description/

    打家劫舍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代码

    对于连续的 nnn 栋房子:H 1 ,H 2 ,H 3 ......H n H~1~,H~2~,H~3~......H~n~H 1 ,H 2 ,H 3 ......H n ,小偷挑选要偷的房子,且不能偷相邻的两栋房子,方案无非两种:

    • 方案一:挑选的房子中包含最后一栋;

    • 方案二:挑选的房子中不包含最后一栋;

    获得的最大收益的最终方案,一定在这两种方案中产生,用代码表述就是:

    最优结果 = 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)是差不多的,唯一区别就是成环了。

    对于一个数组,成环的话主要有如下三种情况:

    情况一:考虑不包含首尾元素

    213.打家劫舍II

    情况二:考虑包含首元素,不包含尾元素

    213.打家劫舍II1

    情况三:考虑包含尾元素,不包含首元素

    213.打家劫舍II2

    注意我这里用的是"考虑",例如情况三,虽然是考虑包含尾元素,但不一定要选尾部元素! 对于情况三,取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




    参考文章:

    第九章动态规划——使用最小花费爬楼梯 https://blog.csdn.net/DDDDWJDDDD/article/details/137244557







    转载本站文章《DP笔记(2):线性动态规划之单线性问题之爬楼梯/打家劫舍》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9109.html