はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
ポイント
-
- 動的計画法(Dynamic Programming)
この記事で得られること
-
- 初歩的な動的計画法の実装
詳細
問題
原文
The Fibonacci numbers, commonly denoted
F(n)form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from0and1. That is,
Given
n, calculateF(n).
Example 1:
Example 2:
Example 3:
Constraints:
0 <= n <= 30
内容(和訳)
フィボナッチ数列は、0と1から始まり、各数は前の2つの数の和であるような数列です。一般にF(n)と表されます。
フィボナッチ数列は、次のように定義されます。
F(0) = 0 F(1) = 1 F(n) = F(n – 1) + F(n – 2)
フィボナッチ数列の最初の10項は、次のとおりです。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
フィボナッチ数列は、自然界に広く見られ、成長、拡散、分岐などの現象に関係しています。また、数学やコンピュータサイエンスにおいても重要な役割を果たしています。
※正しくない可能性があります。
解答
解答1：Python, 動的計画法(Dynamic Programming)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def fib(self, n: int) -> int: dp = [0 for i in range(n+1)] dp[0] = 0 if n==1: return 1 if n==2: return 1 if n > 2: dp[1] = 1 for i in range(2,n+1): dp[i] = dp[i-2] + dp[i-1] print(dp) return dp[-1] |
dpはdynamic programminの頭文字です。
dp配列と呼ばれることがあります。
動的計画法では、入力されるリストなどと同じ長さか、1つ多い数を配列として初期化することがあります。
初期化した配列は、後からfor文を使って問題で求められている値を計算するために段階的に更新されていきます。
フィボナッチ数列では、F(0)=0,F(1)=1,F(2)=1なので、dp配列を初期化した直後に代入しておきます。
nが2よりも大きい場合は、i番目の要素をi-1番目とi-2番目の合計値として計算します。
dp配列の長さはnと同じ(実際には配列外参照にならないように1つ多く用意しました。)なので、
nまでたどり着いたとき、つまりdp配列の最後までたどり着いたとき、F(n)の値が含まれています。
要確認＋復習。
終わりに
補足・参考・感想
問題を分類しました。テーマごとに集中して問題を解くことができます。
LeeetCodeの問題をアルゴリズムとデータ構造による分類
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。
疑問が解決した方は他の問題もどうぞ
前：1768. Merge Strings Alternately
コメント