こんにちは
今回の学びは
・dpはまずはサンプルを埋めてパターンをあぶりだす。そして言葉にして検証する
・import遅いからパフォーマンス欲しい時は削げ
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
brute forceで O(2^(m+n))
dpでO(m+n)です
実際の実装はこちら
前回の問題といい今回の問題もすんなり解法にたどり着けたので
dpの基本がしっかり身についてきた
と実感しています
実装後です。timespace analysis (時間とスペースの分析）は
brute forceで O(2^(m+n))
dpでO(m+n)です
パフォーマンスですが、下位10％と良くないです。ここで疑問です
非常にシンプルなdp実装でこの結果とは他の人はどのような実装で良い
パフォーマンスをたたきだしているのでしょうか？
ということですこしのぞいています。
たとえばこれ（[Python3] Dynamic programming）上位２５％です。でも回答ベースは私と全く同じです
def uniquePaths(self, m: int, n: int) -> int:
dp = [ [0 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
細かいimportの違いが大きいのでしょうか？
実際import抜いて走らせましたらば、、、はい！！見事いきなり上位２５％に入りました
つまりimport遅いからパフォーマンス欲しい時は削げ
という学びを得ました
後は数学てきなアプローチをしている人も！フィボナッチ的な匂いは私もわかりましたよ。でも実際つかって解法だしているのなると、だいぶ上手ですね。
こちらの方も同じdpの解法だけど初期化とか、無駄を極限削ぎ落としている回答です。ただしパファーマンスは上がっておりません。つまり初期化や私がやっているループ中のvalidation(if文と参照)くらいならパフォに影響なしということも分りました。でもこの辺ケースbyケースなので今回のこの一回の事象を信じるわけではないですが、参考までにのメモとしておきます。
まとめ
・dpはまずはサンプルを埋めてパターンをあぶりだす。そして言葉にして検証する
・import遅いからパフォーマンス欲しい時は削げ
以上です