概念の説明
動的計画法については多くの情報がありますが、正式には「多段階のプロセスを、段階間の関係を利用して1つずつ解く一連の単一段階の問題に変換すること」と定義されています。この概念における段階間の関係とは、実際には状態遷移方程式を指します。多くの人がDPは難しいと思っていますが、その根本的な理由は、DPがいくつかの固定形式のアルゴリズムと異なるため、それは最初のステップ、2番目のステップで何をするかを指定する実際のステップを持っていないので、正確に、DPは実際には問題解決のアイデアの一種です。
この考え方の本質は、下の図に示すように、比較的大きなスケールの問題は、いくつかの小さなスケールの問題の結果によって得られるということです。
では、大問題に到達するためには、どのように小問題を処理していけばよいのでしょうか？これが状態遷移方程式です：
opt ：特別な計算論理を指し、通常は最大または最小である。
i,j,k すべてDP方程式で使われるパラメータを定義している。
dp[i] = opt(dp[i-1])+1
dp[i][j] = w(i,j,k) + opt(dp[i-1][k])
dp[i][j] = opt(dp[i-1][j] + xi, dp[i][j-1] + yj, ...)
どの状態移行の式も、多かれ少なかれ微妙なニュアンスがあります。これは実は非常に理解しやすいことで、世の中には非常に多くの関係があり、適用できる公式を抽象化することは不可能なのです。ですから個人的には、すべての種類の状態移動方程式を暗記することはお勧めしません。しかし、DPの問題は分析するために把握し、分類することがまったく不可能だというのは本当でしょうか？私はそうは思いません。このシリーズでは、動的計画法のトピックを簡単なものから深いものまで説明します。
トピック分析
DPの概念に慣れるために、最も簡単なDPの問題から始めましょう：
| 階段を登っているとします。頂上まで登るにはn段の階段が必要です。一度に登れる段数は1段か2段です。あなたは何通りの登り方ができますか。 **注：** 与えられるのは正の整数です。 |
例1：
入力: 2 出力: 2 解説: ビルの最上階に登るには2つの方法がある。
1. 1 + 1
2. 2
例2：
入力：3 出力：3 解説：ビルの最上階に登るには3つの方法がある。
1. 1 + 1 + 1
2. 1 + 2
3. 2 + 1
グラフ解析
解析から明らかなように、この問題は最適部分構造を含むいくつかの部分問題に分解できること、すなわち、その部分問題の最適解からその最適解を効率的に構成できることがわかります。大きな問題をいくつかの小さな問題に分解する」という条件を満たすこと。 dp[n]をn次まで到達できる手法の総数とすると、次の状態遷移方程式が得られます：
1段上がる：道は1つ。
2ステップアップ：1+1と2ウェイ。
3ステップ上がる：ステップ3に到達する方法の総数は、ステップ1と2に到達する方法の数の合計です。
n段上がる場合、n段目に到達する方法の総数は、1段目に到達する方法の数と1段目に到達する方法の数の和になります。
GO言語の例
以上の分析から、コードは以下のようになります：
func climbStairs(n int) int {
if n == 1 {
return 1
}
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。
