LeetCode日本語修行16日目- [403-川を渡るのカエル]

Frog Jump

参考：https://leetcode.com/problems/frog-jump/

問題の内容:

カエルが川を渡ったいです。川はいくつかの単位に分かれていて、それぞれの単位には石があったりなかったりします。カエルは石の上に飛び乗ることはできますが，水の中に入らない。。。？？？
石の位置（単位）を昇順に並べたリストが与えられたとき、カエルは最後の石に着地して川を渡ることができるかどうかを判断します。最初、カエルは最初の石の上にいて、最初のジャンプは1単位でなければならないと仮定します。
カエルの最後のジャンプが k 単位だった場合、次のジャンプは k - 1, k, k + 1 単位のいずれかでなければなりません。カエルは前進方向にしかジャンプできません。

例:

例1:
Input: stones = [0,1,3,5,6,8,12,17]
Output: true

0 -> 1 -> 3 -> 5 -> 8 -> 12 -> 17

例2:
Input: stones = [0,1,2,3,4,8,9,11]
Output: false
0 -> 1 -> 3 -> 4 -> X(前のジャンプは 4-3 = 1，次の単位にジャンプ範囲は
（1-1 ~ 1+1 ）、次の単位は8，距離は４ )

ヒント:

2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0

先ずは　対応のDPの　2DArrayを作ります
dp[石の位置（単位）の数字][前回ジャンプの距離]
今はdp[i][k]
前回は以下の条件の中に必ず一つがtrueです
dp[j][k-1]
dp[j][k]
dp[j][k+1]
即ち
条件１：dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1]
そして：
最初の一回と二回の　石の位置（単位）の数字と一回のジャンプが固定です、
そして、この後石の位置（単位）の数字が増えるの事は確定です、
その対応の石の位置（単位）が固定の+=1です
ジャンプはkから k-1 k k+1三つの可能性

jump[0] = 0　　 前回ジャンプ
stones[0] = 0　　　　　　　石の位置（単位）の数字
index 0　　　　　　　　　　　石の位置（単位）

jump[1] = 1　　　　　　　
stones[1] == 1　　
index 1　　　

jump[2] = 1,2　のどれが　
stones[2] = 2,3 のどれが
index 2

jump[3] = 1,2,3. min = 1 max = 3
stones[3] 表示の必要がない
index 3

以上の条件から、以下の結論を導き出す：
条件2：k≤i
k = stones[i] - stones[i-1] & k≤i
->条件3：stones[i] - stones[i-1] <= i

class Solution {
    fun canCross(stones: IntArray): Boolean {
        var n = stones.size
        var dp = Array(n, { BooleanArray(n) })
        dp[0][0] = true
        for(i in 1 until n){
            ///条件3
            if( stones[i] - stones[i-1] > i){
                return false
            }
            for(j in i - 1 downTo 0){
                var k = stones[i] - stones[j]
                ///条件2
                if(k > j + 1){
                    break
                }
                ///条件1
                dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1]
                if(i == n - 1 && dp[i][k]){
                    return true
                }
            }
        }
        return false
    }   
}