带你读《图解算法小抄》二十一、动态规划（4）

带你读《图解算法小抄》二十一、动态规划（3）https://developer.aliyun.com/article/1347962?groupCode=tech_library

6.跳跃游戏

1）题目描述

给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

2）解题步骤

为了判断是否能够到达最后一个位置，我们可以使用动态规划的思想来解决问题。

• 定义状态：我们可以将问题转化为每个位置是否可达的状态。令 dp[i] 表示位置 i是否可达。
  
• 初始状态：根据题目的约束，起始位置肯定是可达的。即 dp[0] = true。
  
• 状态转移方程：对于位置 i，我们需要检查前面的所有位置是否可达，并且能够跳到 i。如果存在一个可达的位置 j，且能够跳到 i，那么位置 i 也是可达的。因此，状态转移方程为 dp[i] = dp[j] && (j + nums[j] >= i)，其中 0 <= j < i。
  
• 最终解：问题的解即为最后一个位置的可达性，即 dp[n-1]，其中 n 是数组的长度。
  

下面是使用动态规划解决跳跃游戏问题的算法框架：

function canJump(nums) {
  const n = nums.length;
  if (n === 0) {
    return false;
  }  const dp = new Array(n).fill(false);
  dp[0] = true;  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && j + nums[j] >= i) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n - 1];
}

7.爬楼梯

1）题目描述

你正在爬楼梯。它有 n 阶台阶，每次你可以爬 1 阶或 2 阶。你有多少种不同的方法可以爬到楼梯的顶部？

2）解题步骤

为了计算爬楼梯的不同方法数，我们可以使用动态规划的思想来解决问题。

• 定义状态：我们可以将问题转化为每个台阶的不同方法数。令 dp[i] 表示爬到第 i个台阶的不同方法数。
  
• 初始状态：根据题目的约束，当台阶数为 1 时，只有一种方法；当台阶数为 2时，有两种方法。即 dp[1] = 1，dp[2] = 2。
  
• 状态转移方程：对于第 i 个台阶，我们可以从第 i-1 个台阶爬一阶上来，或者从第 i-2 个台阶直接跨两阶上来。因此，状态转移方程为 dp[i] = dp[i-1] + dp[i-2]。
  
• 最终解：问题的解即为爬到最后一个台阶的不同方法数，即 dp[n]，其中 n 是台阶的总数。
  

下面是使用动态规划解决爬楼梯问题的算法框架：

function climbStairs(n) {
  if (n === 1) {
    return 1;
  }  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

带你读《图解算法小抄》二十一、动态规划（5）https://developer.aliyun.com/article/1347959?groupCode=tech_library