Python |ダイナミックプログラミングクラシックケース
動的プログラミングの原則##
動的プログラミングアルゴリズムは、解決する問題を一連の重複するサブ問題に分割し、再発関係を通じて各サブ問題の解決戦略を定義し、いつでもサブ問題の解決策を記録し、最終的に元の問題の解決策を取得して、重複を回避します。サブ問題の繰り返しの解決。
動的計画の要点##
動的プログラミングアルゴリズムには、最適な下部構造、境界、および状態遷移関数の3つの要素があります。
最適な下部構造：各ステージの最適な状態は、前のステージの1つまたはいくつかの状態から直接取得できます。##
境界：問題の最小サブセットの解決策;
状態遷移関数：あるステージから別のステージへの遷移の特定のモード。2つの隣接するサブ問題間の関係を記述します。
最長の昇順サブシーケンス問題##
順序付けられていない整数配列が与えられた場合、最も長い昇順のサブシーケンスの長さを見つけます。
1. 例####
入力：[10,9,2,5,3,7,101,18]
出力：4
説明：最も長い昇順のサブシーケンスは[2,3,7,101]であり、その長さは4です。
2. 問題解決のアイデア：####
ステータス定義：####
入力リストnumsと同じ長さのリストdpを作成します。dp[i]の値は、numsの最初のi桁の最長のサブシーケンスの長さを表します。
3. 最適な下部構造：####
dp [i]を計算するときは、[0、i）のリスト間隔をトラバースして、判断を下す必要があります（j∈[0、i））：####
（1）nums [i]> nums [j]の場合、これは昇順のサブシーケンスであるため、dp [i] = dp [j] +1
（2）nums [i]> nums [j]の場合、これは昇順のサブシーケンススキップではありません####
4. 伝達方程式：dp [i] = max（dp [i]、dp [j] +1）####
5. 初期状態：各要素は少なくとも個別にサブシーケンスになることができ、すべてのdpリストのすべての要素の初期値は1 ####です。
| class Solution: def lengthOfLIS(self, nums) : len_nums=len(nums) dp=[1 for i in range(len_nums)] for i in range(1,len_nums): for j in range(i): if nums[i]>nums[j]: dp[i]=max(dp[i],dp[j]+1) return max(dp) |
総括する＃＃＃＃
上記はこの記事のすべての内容です。動的プログラミングを学び始めたばかりの場合は、理解していなくても心配しないでください。動的プログラミングコードは追跡可能であり、より類似したトピックを練習する必要があります。誰にとっても、この質問に対する他の解決策があります。読者がもっとコミュニケーションを取り、参考のためにメッセージ領域にコードを投稿できることを願っています。
END
チーフエディター|ワンナンラン
責任ある編集者| KeeCTh
**能力が強いほど、責任は大きくなります。事実から真実を求め、厳密かつ細心の注意を払ってください。 ****
** -where2goチーム**