• 它将一个问题分解为相互重叠的子问题，通过反复求解子问题来解决原来的问题

image.png

  • 定义子问题：F(n) = F(n-1) + F(n-2)
  • 反复执行：从2循环到n，执行上述公式

image.png

  • 分而治之：子问题相互独立
  • 动态规划：子问题相互重叠

    题目：

    1.爬楼梯 - 70

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

思路：

  • 爬到第n阶可以在第n-1阶爬1个台阶，或者在第n-2阶爬2个台阶
  • F(n) = F(n-1) + F(n-2) 爬到第n阶的方法是爬到第n-1阶的方法的数量+爬到第n-2阶的方法的数量之和
  • 相互重叠的子问题：动态规划

解题步骤：

  • 定义子问题：F(n) = F(n-1) + F(n-2)
  • 反复执行：从2开始循环n，执行上述公式
  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var climbStairs = function(n) {
  6.     // 处理边界问题
  7.     if(n < 2) return 1
  8.     // 定义初始结果数组
  9.     let dp = [1,1]
  10.     for(let i = 2;i<=n;i++) {
  11.           // 执行公式
  12.         dp[i] = dp[i-1] + dp[i-2]   
  13.     }
  14.       // 返回第n阶时的方法种数
  15.     return dp[n]
  16. };
  18. /**
  19.  * 优化空间复杂度
  20.  * @param {number} n
  21.  * @return {number}
  22.  */
  23. var climbStairs = function(n) {
  24.     // 处理边界问题
  25.     if(n < 2) return 1
  26.       // 初始化定义f(0)和f(1)
  27.       // 代表数组为0时的种数，即原来的n-1 
  28.     let dp0 = 1
  29.     // 代表数组为0时的种数，即原来的n
  30.     let dp1 = 1
  31.     for(let i = 2;i<=n;i++) {
  32.           // 临时变量，记录原来n-1时的
  33.         const temp = dp0
  34.         // dp0前移动一位，变成dp1的值
  35.         dp0 = dp1
  36.           // 新的dp1为 n-1 + n-2，即原来的n和n-1 
  37.         dp1 = dp1 + temp
  38.     }
  39.     return dp1
  40. };
  • 时间复杂度：有一个for循环，O(N)
  • 空间复杂度：临时数组，数量线性增加，O(N) 优化后为O(1)

2.打家劫舍 - 198

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

思路：

  • f(k) = 从前k个房屋中能偷到的最大数额
  • Ak = 第k个房屋的钱数
  • f(k) = max(f(k-2) + Ak, f(k-1))，拆分为3个房间的寻找思维，用第一个房间和第三个房间的钱数和第二个房间的钱数做比较，取最大值，进行拆分
  • 考虑使用动态规划

解题步骤：

  • 定义子问题：f(k) = max(f(k-2) + Ak, f(k-1))
  • 反复执行：从2执行到n，执行上述公式 ```javascript /**
    • @param {number[]} nums
    • @return {number} */ var rob = function(nums) { // 处理特殊值 if(nums.length < 1) return 0 // 定义数组用来存放n-1和n个房间时拿到的钱数 const dp = [0, nums[0]] for(let i = 2; i<= nums.length; i++) {
      1.   // 输入公式，有n个房间的时，
      2.   //能拿到的钱数为 第n-2房间时的最大钱数 + 第n房间的钱数 与第n-1房间钱数的最大值
      3. dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1])
      }
      1. // 返回数组的最后一位
      return dp[nums.length]

};

/**

  • 优化空间复杂度
  • @param {number[]} nums
  • @return {number} */ var rob = function(nums) { // 处理特殊值 if(nums.length < 1) return 0 // 初始化定义f(0)和f(1) // 定义n-1时，拿到的最大钱数 let dp0 = 0 // 定义n时，拿到的最大钱数 let dp1 = nums[0] for(let i = 2; i<= nums.length; i++) {
    1.    // dp0前移了，所以定义临时变量，用来存储n-2时，拿到的最大钱数
    2.  const temp = dp0
    3.  // dp0前移，现在变为dp1，相当于右变为n-1
    4.  dp0 = dp1
    5.    // 输入公式，因为数组长度+1则原来的dp1 变为dp0，新的dp1的公式为
    6.    // 在n-2时的最大钱数+第k个房间的钱数 和原来n-1的最大钱数作对比
    7.  dp1 = Math.max(temp+ nums[i-1] , dp1)
    } return dp1

}; ```

  • 时间复杂度：O(N)，nums的长度
  • 空间复杂度：O(N)，优化后为O(1)