題目

https://leetcode.com/problems/jump-game/

題解

又是經典套路，暴力遞歸->傻緩存->DP

沒寫草稿，直接看代碼吧

class Solution {public boolean canJump(int[] nums) {// 【Solution 1】暴力遞歸 // return process1(0, nums);// 【Solution 2】傻緩存 // return process2(0, nums, new int[nums.length]);// 【Solution 3】自底向上的dpboolean[] dp = new boolean[nums.length];dp[nums.length - 1] = true;for (int i = nums.length - 2; i >= 0; i--) {for (int j = 1; j <= nums[i]; j++) {if (i + j >= nums.length - 1) {dp[i] = true;break;}if (dp[i + j]) {dp[i] = true;break;}}}return dp[0];}// 【Solution 2】dp數組含義: 0=未知 1=true -1=falsepublic boolean process2(int i, int[] nums, int[] dp) {if (i >= nums.length - 1) return true;if (dp[i] != 0) return dp[i] == 1;for (int j = 1; j <= nums[i]; j++) {if (process2(i + j, nums, dp)) {dp[i] = 1;return true;}}dp[i] = -1;return false;}// 【Solution 1】遞歸含義：從i位置開始跳，能不能到終點？public boolean process1(int i, int[] nums) {if (i >= nums.length - 1) return true;for (int j = 1; j <= nums[i]; j++) {if (process1(i + j, nums)) return true;}return false;} }

總結

以上是生活随笔為你收集整理的leetcode 55. Jump Game | 55. 跳跃游戏（暴力递归-＞傻缓存-＞DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。