LeetCode "45. Jump Game II"に、Dijkstra's algorithmで挑んだ話

Time Limit Exceededです。whileの中で線形探索を毎回おこなっているのが、おそらくの原因です。

#問題

>
>非負整数の配列numsが与えられています。あなたは、開始時には配列の最初のインデックスにいます。
>
>配列の各要素は、その位置から最大で跳べる幅を表しています。
>
>あなたの目標は、最小の跳んだ回数で、最後のインデックスにたどり着くことです。
>
>常に最後のインデックスにたどり着くと仮定して大丈夫です。
>

問題は、ここから挑戦できます。
https://leetcode.com/problems/jump-game-ii/

#方針

今いるインデックスから次に行くインデックスへ跳んだ回数は、グラフ理論いうところの距離として表現できます。

スタート地点から、グラフ内の全地点の最短の距離を求めるアルゴリズムとして、Dijkstra's algorithmがあります。

Dijkstra's algorithmは、負の値の距離があると使うことができません。今回は、跳んだ回数という正の値しかとらない数字を距離として使うので、Dijkstra's algorithmを使えます。



ダイクストラのアリゴリズムについては、私は『予備校のノリで学ぶ「大学の数学・物理」』で学びました。

グラフ理論⑤(ダイクストラのアルゴリズム)： https://www.youtube.com/watch?v=X1AsMlJdiok

動画の黒板にはこう書いていあります。

>
>1　始点に0を書き込む
>2　未確定の地点の中から最も小さい値をもつ地点を1つ選び、その値を確定させる（ルート記憶）
>3　2で確定した地点から直接つながっていて、かつ未確定な地点に対し、かかる時間を計算し、画期込まれている数より小さければ更新する
>4　全ての地点が確定していれば終了、そうでなければ2に戻る
>

今回は、すべての地点の最短距離を求める必要はありません。一番最後のインデックスへの最短距離が、欲しい値です。一番最後のインデックスへの最短距離が求まったら、そこで値を返して終了するようにしましょう。

そのため、今回はこのようにします。

>
>1　始点に0を書き込む
>2　未確定の地点の中から最も小さい値をもつ地点を1つ選び、その値を確定させる（ルート記憶）。ただし、複数の地点が最小だった場合、最も配列の終わりに近い地点を選ぶ
>3　2で確定した地点から直接つながっていて、かつ未確定な地点に対し、かかる時間を計算し、画期込まれている数より小さければ更新する
>4　一番最後のインデックスが確定していれば終了、そうでなければ2に戻る
>

#コード

```py

import copy

class Solution:
    
    def jump(self, nums: List[int]) -> int:
        # len(nums)は何度も使いそうなので、予めもらっちゃう。
        len_nums = len(nums)

        default_dict = {'distance': float('inf'), 'is_ditermined': False}

        # ノードを作る。
        nodes = [copy.deepcopy(default_dict) for _ in range(len_nums)]

        #1　始点に0を書き込む
        nodes[0]['distance'] = 0

        # 4　一番最後のインデックスが確定していれば終了、そうでなければ2に戻る
        while not nodes[-1]['is_ditermined']:
            # 2　未確定の地点の中から最も小さい値をもつ地点を1つ選び、その値を確定させる（ルート記憶）。
            # ただし、複数の地点が最小だった場合、最も配列の終わりに近い地点を選ぶ

            # 線形探索を行うために、候補の場所を記録する辞書(cur_min)を作る。
            cur_min = {'index': len_nums, 'value': float('inf')}
            for i, node in enumerate(nodes):
                node_distance = node['distance']
                if not node['is_ditermined']\
                and node_distance <= cur_min['value']\
                and node_distance != float('inf') :
                    cur_min['index'] = i
                    cur_min['value'] = node_distance

            # cur_minで示されるnodeを確定させる。
            # 線形探索は、配列の左端から右端へと行われているので、
            # 「ただし、複数の地点が最小だった場合、最も配列の終わりに近い地点を選ぶ」は達成されている。

            #何回もcur_min[index]を書くのが面倒なので、curに省略する。
            cur = cur_min['index']

            nodes[cur]['is_ditermined'] = True

            # cur_min[index]から跳べる場所全てについて考える。
            for i in range(nums[cur] + 1):
                # 3　2で確定した地点から直接つながっていて、かつ未確定な地点に対し、
                if not nodes[min([len_nums -1, cur + i])]['is_ditermined'] :
                    # かかる時間を計算し、書き込まれている数より小さければ更新する
                    # 跳びすぎてnumsのrangeを突き抜けないように、minで押さえつける。
                    nodes[min([len_nums -1, cur + i])]['distance']= min([nodes[min([len_nums -1, cur + i])]['distance'], cur_min['value'] + 1])

        return nodes[-1]['distance']

```

結果：**Time Limit Exceeded**
![TimelimitExceeded.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1851956/37d70376-16a0-202e-9e2a-b107b3f817dd.png)

#反省
おそらく、whileの中で線形探索を毎回おこなっているのが、Time Limit Exceededの原因だと思います。
ただ、もう午前2時なので、これを解決するには遅すぎます。
続きは、また次回に！
ストゼロ飲んで寝ます！

#追記：結局、どうすれば解けるのか

https://leetcode.com/problems/jump-game-ii/discuss/170518/8-Lines-in-Python!-Easiest-Solution!

ここで提供されている解答がとてもシンプルです。

```py

class Solution:
    def jump(self, nums: List[int]) -> int:

        # numsの長さが1以下の時には、0を返す。
        if len(nums) <= 1:
            return 0

        # ポインターを2つ用意する。
        # lの初期値は0。
        # rの初期値は、lの初期値から跳べる最大の場所。
        l = 0
        r = nums[0]

        # ここまでアルゴリズムが来ているということは、1回の跳躍は確定している。
        times = 1

        # ポインターrが、numsの端を
        end = len(nums) - 1
        while r < end:
            #跳躍回数を1回加算する
            times += 1
            # 今回の跳躍では、rまでは到達できることが保証されている。
            # そのため、rの値を次のステップのlにすることができる。
            # 今回の跳躍で、現在のrを越えるもののうちの最大値を、
            # 次のステップのrにする。
            # l番目からr番目までにある各iについて、
            # i番目から、nums[i]だけ跳んだものの最大値を、次のステップのrにする。
            next_r = max(i + nums[i] for i in range(l, r + 1))
            l = r
            r = next_r
        return times


```

![LR.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1851956/110f4d08-74d0-e7d6-1ec4-5ced6a9a0aa4.png)


こんなの、思いつかねーぜ！