こんにちは
今回の学びは
・アイデアタイマーセット5分ヨーイドンといメリハリ
・LTE(Time Limit Exceeded)はtime complexityの大きなヒントである
・連続という特性をうまく利用
・連続という特性は位置変数で表現できる
・アイデアに見切りをつけるための条件を考える
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
[3, 2, 11, 7, 4]
*
最初のポジションから、最大その数、右に移動できて
それをくりかえして最後のindexにたどり着くことができるか？
という問題
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
最初のポジションで選択してはS[0]つまり最大S[0]の配列の積という膨大な選択肢になることわかる
なので ブルートフォースはダメだなと思う
ホワイトボードをつかって
サンプルをあーだこーだしました。
で
dpっぽことができるんですよ。
ループしてそのS[i]の数分、右のdp[i+x]にTrueいれていく
最終的に最後のdp[-1]がTrueだったokというふうにします。
pseudocode（擬似コード）をかいてみますか。
dp初期化
for i in range(len(S)):
for n in range(1, S[i]+1):
dp[i+n] += 1
return True if dp[i] > 0 else False
実際の実装はこちら
class Solution:
def canJump(self, nums: List[int]) -> bool:
length = len(nums)
if length <= 0: return False
if length == 1: return True
dp = [0] * length
dp[0] = 1
def dp_print():
for row in dp:
logging.debug(row)
def dp_valid(i):
if i < 0 or i >= length: return False
else: return True
def dp_get(i, default=0):
if dp_valid(i): return dp[i]
else: return default
for i in range(length):
if dp[i] > 0:
for n in range(nums[i]):
if dp_valid(i+n+1):
dp[i+n+1] += 1
return True if dp[i] > 0 else False
いつもの感じで解けたかとおもいきや
TLE
。。。
おー、そうか
こちらの濃厚なテストケースなのね。
O(n * S[i])なのでだめなのね。
なにか他に思いつくアイデアはないか。
模索しましょう
タイマーセット5分ヨーイ、どん！
10分くらいで一個おもいついきましたのでが、こちら。題して
「どこまでいけるかチケット更新リレー！」
どんどんぱふぱふ
これはジャンプできるのが与えられた数字だけではなく、その数字以下なら
いくらでも飛べるということは
どこのindexまでは行けるんだという情報と考えられます。
これは、すばらし発想で
これまでは、例えばnums[3] = 7だったとしたら、次の7つの配列にジャンプできるのでそれぞれのdp[4, 5, ... ,10]にTrueなりをセットしてきました、
この情報って
index 10までジャンプできます
という、一言でいいあらわせます。
これはジャンプできるのが次の連続するｘステップという特性を利用しているということです。別の言い方をすると
連続という特性をうまく利用しています
ジャンプでいるのは、次の連続するxステップ、というようなことが
わかったら是非、連続という特性を利用できないか考えてみてください
傾けると、次のように覚えてもいいでしょう。
連続という特性は位置変数で表現できる
そうすると、これまではすべてのindexにTrueを代入してきたコストが
この最高ジャンプ到達地点のindexの伝搬して更新するだけでよくなります。
行けそうなきがします。
あと、もうひとつアイデアの発想のおいて重要なポイントがあったので言っておきます。
この問題を、どうやってとくか考えるプロセスで、
一番最後のindexに来れればいいのだから、逆算で、最後のindexに来るためには、どのindexにいる必要があるか？と考えます。逆算は柔軟でとてもいい考えかたです。しかし、この問題の場合、どこのindexにいる必要があるかとう、とう問いにたいする答えは、別にどのindexからでも最後までと立つできる可能性はある、とうものでパターン数が多すぎて、役に立たないことがわかります。ですので、この時点で逆算という着想を捨てることができます。
すると前から情報を伝播する、というような方向性に絞り込むことができ。
正解のアルゴリズムの着想までのスピードがあがったはずです。なので
このしっかり方向性やとあるアイデアに見切りをつけられるか、はとても重要で今回のように見切りをつけるための項目を見つけ出し、満たしていなければ切り捨てるというテクニックは、とても大事です。
ということで
アイデアに見切りをつけるための条件を考える
というのも今回の学びにいれておきます
実装します
class Solution:
def canJump(self, nums: List[int]) -> bool:
length = len(nums)
if length <= 0: return False
if length == 1: return True
dp = [0] * length
def dp_valid(i):
if i < 0 or i >= length: return False
else: return True
carryover_idx = 0
for i in range(length):
x = nums[i]
possible_best_jumping_idx = i + x
if dp[i] < i: return False
carryover_idx = max(possible_best_jumping_idx, carryover_idx)
if dp_valid(i+1):
dp[i+1] = carryover_idx
return True
見事クリアです
ということで
実装後です。timespace analysis (時間とスペースの分析）は
最初の通らなかったtime complexityは O(n * nums[i])で
通ったtime complexityは O(n)でした
今回は、LTE出て苦戦しましたが
そこから自力でアイデア発想から実装までもっていけたのは良かった点です。
試しにアイデアタイマーセット5分ヨーイドンといメリハリはよかったとおもいます。全くそこでアイデアが出てこなければヒントや回答を見るつもりでした。
着想自体もサンプルを見返すということと
現在のtimecomplexityで通らなかったのだから
というのは実はたいへん大きなヒントで、
ヒントでO(n * nums[i])では通りません
と書かれていたら、誰でも、頭をひねり出す、他にもっとよいアルゴリズム、工夫があるはずだと！と考え出します。
なので、その情報を自分であぶり出せばよい
つまり、今回、最初にやったアルゴリズムのtime complexityをしっかり分析できていれば O(n * nums[i])ということが分り、
なんとか、O(n)に持っていけないかと考えられるのです。
こうかんがえると、最初のLTEはヒントをあぶり出すための１手で
大変有効だし、全然無駄ではなく必要でかつ、むしろ無駄のない１手だったと思います。time complexityがO(n * nums[i])ではダメという大きなヒントはアイデア着想の手がかりということ
を身を持って感じました。
LTE(Time Limit Exceeded)はtime complexityの大きなヒントである
もちろん
time complexityを分析する能力が重要である
といことの理由の一つだなー、と感じることができたかとおもいます。
まとめ
・アイデアタイマーセット5分ヨーイドンといメリハリ
・LTE(Time Limit Exceeded)はtime complexityの大きなヒントである
・連続という特性をうまく利用
・連続という特性は位置変数で表現できる
・アイデアに見切りをつけるための条件を考える
以上です
ちなみにこの最後の回答、削ぐとdpはいらないことがわかります。
しかしアイデア的には前の状態を引き継ぐなんかは一種のdpとかんがえてもいいかしれません。
class Solution:
def canJump(self, nums: List[int]) -> bool:
length = len(nums)
if length <= 0: return False
if length == 1: return True
carryover_idx = 0
for i in range(length):
if carryover_idx < i: return False
carryover_idx = max(i + nums[i], carryover_idx)
return True
以上です。