一、跳躍游戲

55. 跳躍游戲 - 力扣（LeetCode）https://leetcode.cn/problems/jump-game/description/?envType=problem-list-v2&envId=dynamic-programming

class Solution {
public:bool canJump(vector<int>& nums) {// 狀態定義： dp[i]表示該點是否能夠達到// 狀態轉移： dp[i] = for j in i: if dp[j]: dp[i] = tbool dp[nums.size() + 1];dp[0] = true;for (int i = 1; i < nums.size(); i++) {dp[i] = false;for (int j = 0; j < i; j++)if (j + nums[j] >= i)dp[i] |= dp[j];}return dp[nums.size() - 1];}
};

狀態定義如代碼所示，狀態轉移時從前往后依次選擇能到達i點的地方更新dp[i]

二、跳躍游戲II

45. 跳躍游戲 II - 力扣（LeetCode）https://leetcode.cn/problems/jump-game-ii/?envType=problem-list-v2&envId=dynamic-programming

class Solution {
public:int jump(vector<int>& nums) {// 狀態定義： dp[i]表示到達第i個點的最小跳躍次數// 狀態轉移： dp[i] = min(all can jump dp of j) + 1int n = nums.size();int dp[10100];for (int i = 0; i < n; i++) dp[i] = n + 1;dp[0] = 0;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (j + nums[j] >= i)dp[i] = min(dp[i], dp[j]);}dp[i] += 1;}return dp[n - 1];}
};class Solution {public int jump(int[] nums) {int n = nums.length;int[] dp = new int[n];for (int i = 0; i < n; i++) dp[i] = n + 1;dp[0] = 0;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++)if (j + nums[j] >= i)dp[i] = Math.min(dp[i], dp[j]);dp[i] += 1;}return dp[n - 1];}
}class Solution:def jump(self, nums: List[int]) -> int:n = len(nums)dp = [n + 1] * ndp[0] = 0for i in range(1, n):for j in range(0, i):if j + nums[j] >= i:dp[i] = min(dp[i], dp[j])dp[i] = dp[i] + 1return dp[n - 1]

與上題不同的是本題在一定能到達的情況下求出最小跳躍次數，狀態定義如代碼所示，狀態轉移更新策略同一