LeetCode中級-ジャンプゲーム

ジャンプゲーム
非負の整数配列を指定すると、最初に配列の最初の位置に位置します.
配列内の各要素は、その位置でジャンプできる最大長を表します.
あなたが最後の位置に着くかどうかを判断します.
例1:

  : [2,3,1,1,4]
  : true
  :     0   1   1  ,     3          。

例2:

  : [3,2,1,0,4]
  : false
  :     ，         3    。             0 ，                 。

ぶんせき
i番目の位置から下にジャンプできるステップ数を直接考慮すると、2つの場合があり、前の隣接位置のステップ数を起点とするか、nums[i]-1ステップをジャンプすることができます.あるいは、ある位置からn回ジャンプしてiに着いたときの残りのステップ数を記録します.
このとき、前の位置からジャンプした後の残りのステップ数と隣接しない位置からジャンプした残りのステップ数を直接比較すればいいでしょう.
すなわち,i位置にジャンプしたときの残りの有効ステップ数,すなわちどれだけのステップをジャンプできるかをdp[i]で記録すると,

dp[i] = max(dp[i-1],nums[i-1])-1;

もう1つの解決策は、到達可能な最も遠い位置を計算することです.
コード#コード#

    class Solution {
        public boolean canJump(int[] nums) {
            /*
            //dp[i] = max(dp[i-1] , nums[i-1])-1; 
            //dp[i]   i        
            int[] dp = new int[nums.length];
            for(int i=1;i=0;
            */
            int canReach = 0;
            for(int i=0;iif(i > canReach || canReach > nums.length-1)
                    break;
                canReach = canReach>(i+nums[i])?canReach:(i+nums[i]);
            }
            return canReach>=nums.length-1;
        }
    }