山西省新农村建设网站,宁波网站建设免费咨询,网站建设分金手指专业,cdr平面设计教程一、题目描述
给定一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1#xff1a;
输入#xff1a;nums [2,3,1,1,4] 输出#xff1a;true 解释#x…一、题目描述
给定一个非负整数数组 nums 你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1
输入nums [2,3,1,1,4] 输出true 解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 示例 2
输入nums [3,2,1,0,4] 输出false 解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。
提示
1 nums.length 3 * 104 0 nums[i] 105
二、代码思路
本题与其他题目有明显的区别根据题意我的目的是走到最后下标的位置但是我走的路线或者是跳的位置不是确定的即每一步都是不确定的但是每一步都是有关联的而动态规划就是处理这种决策问题通过对不同状态的决策决定最终情况的产生。
动态规划几步曲
确定状态的意义一般能找到状态的意义就成功一大半了大多数情况下都不知道怎么定义状态确定状态的转换方程即状态与状态之间的联系比如上台阶dp[i] dp[i - 1] 1 or dp[i -2] 2 就是我在本节楼梯的位置我可以跨两格上来也可以跨一格上来。确定状态的初始值。确定遍历的顺序我印象中背包问题有逆序遍历的情况。
三、代码题解
class Solution {public boolean canJump(int[] nums) {//动态规划问题//动态规划就是每一步动态做决策最终达到想要的结果。//dp[i][i - 1] : 第 i - 1的位置是否能走1步到达第i个位置//判断条件dp[i][i - 1] nums[i] i - (i - 1) ? true : false;//状态转换方程dp[i] 是否能到达第i个位置dp[i] nums[j] i - (j) ? true : false;int dp[] new int[nums.length];dp[0] 1;for (int i 1; i nums.length; i) {for (int j 0; j i; j) {if (dp[j] 1 nums[j] (i - j)) {dp[i] 1;break;}}}return dp[nums.length - 1] 1 ? true : false;}
}
