leetcode 55. Jump Game-欲張りアルゴリズム

原題リンク:55.Jump Game
【考え方-Java】欲張りアルゴリズム
本題は欲張りアルゴリズムを採用する.
欲張りアルゴリズム(欲張りアルゴリズムとも呼ばれる)とは、問題を解く際に、常に現在から見て最良の選択をすることを意味する.つまり、全体的な最適化を考慮せずに、ある意味での局所最適解を行う.欲張りアルゴリズムと動的計画アルゴリズムは、いずれも局所最適化からグローバル最適化を導き出すものであり、ここで両者の違いを比較せざるを得ない
欲張りアルゴリズム:1.貪欲アルゴリズムでは,貪欲戦略は前のステップの最適解から次のステップの最適解を導くが,前のステップの前の最適解は保持されないため,各ステップの貪欲決定は変更できない.  2.(1)で紹介したように,貪欲法の正しい条件は,各ステップの最適解が必ず前ステップの最適解を含むことである.
動的計画アルゴリズム:1.グローバル最適解には必ずある局所最適解が含まれるが、必ずしも前の局所最適解が含まれるとは限らないので、前のすべての最適解を記録する必要がある.動的計画の鍵は状態移動方程式であり、すなわち求めた局所最適解からグローバル最適解をどのように導くかである.境界条件:すなわち最も簡単で,直接得られる局所最適解
本題は1つの数reachで到達できる最も遠い下標を表して、一歩一歩歩いて、もしreachの範囲内のどこかで達成できる範囲がreachより大きいことを発見したら、私たちはもっと広い範囲で元のreachを置き換えて、このような局部の最も優れた貪欲な策略は、全局的に見ても最も優れています.局所的に到達可能な最大範囲は、グローバルに到達可能な最大範囲でもあるからです.

public class Solution {
    public boolean canJump(int[] nums) {
        int reach = nums[0];
        for(int i = 1; i < nums.length && reach >= i; i++)
            if(i + nums[i] > reach) reach = i + nums[i];  //    
        return reach >= (nums.length-1) ? true : false;
    }
}

72/72
 test cases passed. Runtime: 2 ms  Your runtime beats 72.95% of javasubmissions.