目錄
問題特性：
最優子結構：
代碼示例：（動態規劃最優子結構）
上述最小代價爬樓梯的運行過程：
代碼示例：
無后效性：
解析：
具體過程圖示如下：
具體的代碼示例：
解析：
問題特性：
動態規劃的基本是通過子問題分解來求解原問題的。但是通俗來說，子問題分解是一種通用的算法思路，在分治、動態規劃、回溯中的側重點也不同。?
- 分治問題：遞歸地將原問題劃分為多個相互獨立的子問題，直至最小子問題，并在回溯中合并子問題的解，最終得到原問題的解
- 動態規劃：對問題進行遞歸分解，但與分治算法的主要區別是，動態規劃中的子問題是相互依賴的，在分解過程中會出現許多重疊的子問題。
- 回溯：在嘗試和回退中窮舉所有的可能的解，并通過剪枝避免不必要的搜索分支。原問題的解由一系列決策步驟構成，我們可以將每個決策步驟之前的子序列看作一個子問題
實際上，動態規劃常用來求解最優化問題，它不僅包含重疊子問題，還具有兩大特性：最優子結構，無后效性。
最優子結構：
給定一個樓梯，你每步可以上1階或者2階，每一個樓梯上都貼有一個非負整數，表示你在該臺階所需要付出的代價。給定一個非負整數數組cost，其中cost[i]表示在第i個臺階需要付出的代價，cost[0]為地面（起始點）。
請計算最少需要付出多少代價才能到達頂部。
若第1，2，3階的代價分別為1，10，1，則地面爬到第3階的最小代價為2.
設dp[i]為爬到第i個臺階付出的代價，由于第i階只能從i-1階或者i-2階走來，因此dp[i]只可能等于dp[i-1] + cost[i] 或者 dp[i-2] + cost[i]。為了盡可能減少代價，我們應該選擇兩者居中較小的那個：
dp[i] = min(dp[i-1],dp[i-2]) + cost[i]
這里就可以直接得出最優字結構的含義：原問題的最優解是從子問題的最優解構建而來。
但是對于爬樓梯的最優子結構，我們又該怎么理解呢，它的目標是求解方案數量，但是我們將其理解稱為最大方案數量，雖然題目的含義一樣，但是在這里出現了最優子結構的痕跡：第n階方案最大數量=第n-1階和第n-2階最大方案數量和。
根據狀態轉移方程，以及初始狀態dp[1] = cost[1]和dp[2] = cost[2]。
代碼示例：（動態規劃最優子結構）
# python 代碼示例
def min_cost_climbing_stairs_dp(cost) :n = len(cost) - 1if n == 1 or n == 2 :return cost[n]dp = [0] * (n + 1)dp[1], dp[2] = cost[1], cost[2]for i in range(3, n + 1) :dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]return dp[n]// c++ 代碼示例
int minCostClimbingStairsDP(vector<int> &cost)
{int n = cost.size() - 1 ;if (n == 1 || n == 2){return cost[n] ;}vector<int> dp(n + 1) ;dp[1] = cost[1] ;dp[2] = cost[2] ;for (int i = 3; i <= n ; i++){dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] ;}return dp[n] ;
}上述最小代價爬樓梯的運行過程：
將上述代碼進行空間優化，將一維壓縮至0維，空間復雜度由O(n)變為O(1)
代碼示例：
# python 代碼示例
def min_cost_climbing_stairs_dp_comp(cost) :n = len(cost) - 1if n == 1 or n == 2 :return cost[n]a, b = cost[1], cost[2]for i in range(3, n + 1) :a, b = b, min(a, b) + cost[i]return b// c++ 代碼示例
int minCostClimbingStairsDPComp(vector<int> &cost)
{int n = cost.size() - 1 ;if (n == 1 || n == 2){return cost[n] ;}int a = cost[1], b = cost[2] ;for (int i = 3 ; i <= n ; i++){int temp = b ;b = min(a, b) + cost[i] ;a = temp ;}return b ;
}無后效性：
能夠有效解決問題的重要特性之一，定義：給定一個確定的狀態，它的未來發展只與當前的狀態有關，而與過去經歷的所有狀態無關。
以爬樓梯進行相關理解，給定狀態i，它會發展出狀態i+1和狀態i+2，分別對應跳1步和跳2步。在做出這兩種選擇時，無須考慮狀態i之前的狀態，它們對i的未來沒有影響。
但是下面這種情況就不一樣了：如題，給定一個共有n階的樓梯，你每一步可以上1階或者2階，但是不能連續兩次跳1階，請問有多少種方案可以爬到樓頂？
如圖所示：爬3階的例子
解析：
如果上一輪跳1階上來的，下一次跳動必須跳2階。這就意味著，下一步的選擇不能由當前狀態（當前所在樓梯階數）獨立決定，還和前一個狀態（上一輪的樓梯的階數）有關。
所以原來的狀態轉移方程dp[i] = dp[i-1] + dp[i-2]也因此失效，為了滿足約束條件，我們不能直接將dp[i-1]直接放入到dp[i]中。
為此，我們需要擴展狀態定義：狀態[i,j]表示處在第i階并且上一輪跳了j階，其中j屬于{1，2}。此狀態定義有效地區分了上一輪跳了1階還是2階，我們可以根據判斷當前狀態從何而來。
- 當上一輪跳了1階時，上上一輪只能選擇跳2階，即dp[i,1]只能從dp[i-1,2]轉移過來
- 當上一輪跳了2階時，上上一輪可選擇跳1階或者跳2階，即dp[i,2]可以從dp[i-2,1]或dp[i-2,2]轉移過來。
因此，在該定義下,dp[i,j]表示狀態[i,j]對應的方案數。狀態轉移方程為：
dp[i,1] = dp[i-1,2]
dp[i,2] = dp[i-2,1] + dp[i-2,2]
具體過程圖示如下：
最終，返回dp[n,1] + dp[n,2]即可，兩者之和代表爬到第n階的方案總數：
具體的代碼示例：
# python 代碼示例
def climbing_stairs_constraint_dp(n) :if n == 1 or n == 2 :return 1dp = [ [0] * 3 for _ in range(n + 1)]dp[1][1], dp[1][2] = 1, 0dp[2][1], dp[2][2] = 0, 1for i in range(3, n + 1) :dp[i][1] = dp[i - 1][2]dp[i][2] = dp[i - 2][1] + dp[i - 2][2]return dp[n][1] + dp[n][2]// c++ 代碼示例
int climbingStairsConstraintDP(int n)
{if (n == 1 || n == 2){return 1 ;}vector<vector<int>> dp(n + 1, vector<int>(3, 0)) ;dp[1][1] = 1 ;dp[1][2] = 0 ;dp[2][1] = 0 ;dp[2][2] = 1 ;for (int i = 3 ; i <= n ; i++){dp[i][1] = dp[i - 1][2] ;dp[i][2] = dp[i - 2][1] + dp[i - 2][2] ;}return dp[n][1] + dp[n][2] ;
}解析：
在上面的約束條件中只需要考慮一個約束對象，因此我們可以通過擴展狀態定義，使得問題重新滿足無后效性，
給定一個共有?i?階的樓梯，你每步可以上?1?階或者?2?階。規定當爬到第?i?階時，系統自動會在第?2i?階上放上障礙物，之后所有輪都不允許跳到第?2i?階上。例如，前兩輪分別跳到了第?2、3?階上，則之后就不能跳到第?4、6?階上。請問有多少種方案可以爬到樓頂？
在這個問題中，下次跳躍依賴過去所有的狀態，因為每一次跳躍都會在更高的階梯上設置障礙，并影響未來的跳躍。對于這類問題，動態規劃往往難以解決。
實際上，許多復雜的組合優化問題（例如旅行商問題）不滿足無后效性。對于這類問題，我們通常會選擇使用其他方法，例如啟發式搜索、遺傳算法、強化學習等，從而在有限時間內得到可用的局部最優解。
