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に戻る

#コード


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

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

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

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

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


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

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