動態規劃--5道題入門
動態規劃是由遞迴一步步優化出來的
遞迴–>記憶化遞迴–>動態規劃
動態規劃與其說是一個演算法，不如說是一種方法論。該方法論主要致力於將合適的問題拆分成三個子目標——擊破：
1。建立狀態轉移方程
2。快取並複用以往結果
3。按順序從小往大算
直接看題吧
比如：
一、斐波那契額數列（劍指offer10-I）
寫一個函式，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項。斐波那契數列的定義如下：
F（0） = 0， F（1） = 1
F（N） = F（N - 1） + F（N - 2）， 其中 N > 1。
斐波那契數列由 0 和 1 開始，之後的斐波那契數就是由之前的兩數相加而得出。
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。
示例 1：
輸入：n = 2
輸出：1
示例 2：
輸入：n = 5
輸出：5
1.最常用的解法，遞迴：
class Solution {
public：
int fib（int n） {
//1。結束條件
if（n<2） return n；
if（n>（1e9+7））return 1；
//2。找等價函式
return （fib（n-1）+fib（n-2））；
}
}；
結果超時，因為一旦要求的n偏大，就會出現大量的重複計算：
2.遞迴+記憶化
：
到達32的時候仍然會超時。按理說應該可以透過1
class Solution {
public：
int fib（int n） {
if（n==0） return 0；
if（n==1） return 1；
vector
//1。結束條件
//mem［0］=0；
//mem［1］=1；
//2。找等價函式
if（mem［n］==-1） mem［n］=（fib（n-1）+fib（n-2））%1000000007；
return mem［n］ ；
}
}；
修改後成功了！！！！！！！！！！！！！！！！！！！！！！！！！！！！
class Solution {
public：
int fib（int n） {
mem=vector（n+1，-1）；
return fibs（n）；
}
private：
vector
int fibs（int n） {
if（n<2） return n；
if（mem［n］==-1） mem［n］=（fibs（n-1）+fibs（n-2））%1000000007；
return mem［n］ ；
}
}；
**總結：
遞迴到記憶化遞迴有三步：
1.將遞迴函式轉換為輔助函式，新建全域性容器，並在主函數里面初始化大小。
2.在輔助函式中新增if條件語句，考慮當陣列容器為-1時的情況
。
3.將遞迴等價關係取得的值記憶到陣列容器中去，最後返回容器。
分開的原因暫時未知！
3.動態規劃
自下而上的解決問題
class Solution {
public：
int fib（int n） {
if（n==0） return 0；
vector
//1。結束條件
mem［0］=0；
mem［1］=1；
//注意for迴圈裡面時三個mem
for （int i = 2； i <= n； i++）{
mem［i］=（mem［i-1］+mem［i-2］）%1000000007；
}
return mem［n］ ；
}
}；
記憶化遞迴到動態規劃總結：
1.又合併只有一個函式，對陣列容器原地進行建立並初始化。
2.把遞迴的結束條件轉換為陣列容器的值。
3.利用遍歷和陣列容器中已存在的值，找到陣列容器中的等價關係，最後返回所需要的容器值。
4.最佳化空間之後
class Solution {
public int fib（int n） {
if（n==0）return 0；
if（n==1）return 1；
int a=0，b=1；
for（int i=2；i<=n；i++）{
int x = （a+b）%1000000007；
a=b；
b=x；
}
return b；
}
}
二、青蛙跳臺問題（劍指offer10-II）
1.遞迴：
class Solution {
public：
int numWays（int n） {
if（n==0）return 1；
if（n==1）return 1；
return numWays（n-1）+numWays（n-2）；
}
}；
2.遞迴+記憶最佳化
因為重複太多，所以需要記憶。
遞迴到記憶化遞迴有三步：
1.將遞迴函式轉換為輔助函式，新建全域性容器，並在主函數里面初始化大小。
2.在輔助函式中新增if條件語句，考慮當陣列容器為-1時的情況
。
3.將遞迴等價關係取得的值記憶到陣列容器中去(注意等價關係的容器陣列下標不再含有n)，最後返回容器。
class Solution {
public：
int numWays（int n） {
mem=vector（n+1，-1）；
return tiaotai（n）；
}
private：
vector
int tiaotai（int n）{
if（n==0）return 1；
if（n==1）return 1；
if（mem［n］==-1）
mem［n］=（tiaotai（n-1）+tiaotai（n-2））%1000000007；
return mem［n］；
}
}；
記憶化遞迴到動態規劃總結：
1.又合併只有一個函式，對陣列容器原地進行建立並初始化。
2.把遞迴的結束條件轉換為陣列容器的值。
3.利用遍歷和陣列容器中已存在的值，找到陣列容器中的等價關係(注意等價關係的容器陣列下標不再含有n)，最後返回所需要的容器值。
3.動態規劃
直接這麼寫輸入0總是報錯
class Solution {
public：
int numWays（int n） {
vector
mem［0］=1；
mem［1］=1；
for（int i=2；i<=n；i++）{
mem［i］=（mem［i-1］+mem［i-2］）%1000000007；
}
return mem［n］；
}
}；
直接把1儲存到所有的陣列元素中反而正確
class Solution {
public：
int numWays（int n） {
//動態規劃4行解決
//宣告n+1大小的vector，+1是要儲存0至n共n+1個數據。
vector
for（int i = 2； i <= n； i++）
v［i］ = （v［i - 1］ + v［i - 2］） % 1000000007；//注意別忘記取餘
return v［0］；//直接返回最後一個數，即最終結果
}
}；
4.空間最佳化：
class Solution {
public：
int numWays（int n） {
vector
if（n<=1）return 1；
int a=1，b=1，c=0；
for（int i=2；i<=n；i++）{
c=（a+b）%1000000007；
a=b；
b=c；
}
return b；
}
}；
或者這種
class Solution {
public：
int numWays（int n） {
//建立一個數組，
//陣列大小盡量大，因為它是可以取的n的最大範圍
int ans［500］={1，1}；
//把每一種臺階數對應的跳法總數存到對應陣列中
for（int i=2；i<=n；i++） ans［i］=（ans［i-1］+ans［i-2］）%（int（1e9+7））；
//返回所取的臺階對應跳法數
return ans［n］；
}
}；
三、 整數拆分（Leetcode343）
給定一個正整數 n，將其拆分為至少兩個正整數的和，並使這些整數的乘積最大化。 返回你可以獲得的最大乘積。
示例 1：
輸入： 2
輸出： 1
解釋： 2 = 1 + 1， 1 × 1 = 1。
示例 2：
輸入： 10
輸出： 36
解釋： 10 = 3 + 3 + 4， 3 × 3 × 4 = 36。
1.普通遞迴（超時）
class Solution {
private：
int Max（int a， int b， int c）{
return max（a，max（b，c））；
}
int _integerBreak（int n）{
//結束條件
if（n==1）return 1；
//尋找等價關係
int res=-1；
for（int i=1； i res=Max（res，i*（n-i）， i*_integerBreak（n-i））； } return res； } public： int integerBreak（int n） { //vector return _integerBreak（n）； } }； 2.記憶化遞迴 class Solution { private： vector int Max（int a， int b， int c）{ return max（a，max（b，c））； } int _integerBreak（int n）{ //結束條件 if（n==1）return 1； //尋找等價關係 if（mem［n］！=-1）return mem［n］； int res=-1； for（int i=1； i res=Max（res，i*（n-i）， i*_integerBreak（n-i））； } mem［n］=res； return res； } public： int integerBreak（int n） { assert（n>=2）； mem = vector return _integerBreak（n）； } }； 3.動態規劃 記憶化遞迴到動態規劃總結： 1.又合併只有一個函式，對陣列容器原地進行建立並初始化。 2.把遞迴的結束條件轉換為陣列容器的值。 3.利用遍歷和陣列容器中已存在的值，找到陣列容器中的等價關係(注意等價關係的容器陣列下標不再含有n)，最後返回所需要的容器值。 class Solution { private： int Max（int a， int b， int c）{ return max（a，max（b，c））； } public： int integerBreak（int n） { assert（n>=2）； vector mem［1］=1； int res=-1； for（int i=2； i<=n； i++）{ for（int j=1；j res=Max（res，j*（i-j）， j*mem［i-j］）； mem［i］=res； } } return mem［n］； } }； 四、三角形求和(Leetcode120) 題意： 給定三角形，每次只能移動到下一行中的相鄰結點，求從頂點到底邊的最小路徑和。 ［ ［2］， ［3，4］， ［6，5，7］， ［4，1，8，3］ ］ 相鄰結點：與（i， j） 點相鄰的結點為 （i + 1， j） 和 （i + 1， j + 1）。 分析： 若定義 f(i, j)f(i,j) 為 (i, j)(i,j) 點到底邊的最小路徑和 ，則易知遞迴求解式為： f（i， j） = min（f（i + 1， j）， f（i + 1， j + 1）） + triangle［i］［j］ 由此，我們將任一點到底邊的最小路徑和，轉化成了與該點相鄰兩點到底邊的最小路徑和中的較小值，再加上該點本身的值。這樣本題的 遞迴解法（解法一） 就完成了。 1.純遞迴的錯誤方法，因為會超時： class Solution { private： int dfp（vector //結束條件 //i，j代表從哪個點一直向下的路徑之和 //下面的條件是i已經超過最底端，所以路徑和返回0 if（i==triangle。size（））return 0； //等價關係 return min（dfp（triangle，i+1，j），dfp（triangle，i+1，j+1））+triangle［i］［j］； } public： int minimumTotal（vector int n = triangle。size（）； //對輔助容器的初始化，初始化後二維陣列的空間值自動賦值為0 return dfp（triangle，0，0）； } }； 暴力搜尋會有大量的重複計算，導致 超時，因此在 解法二 中結合記憶化陣列進行最佳化。 2.遞迴加記憶化的方法： class Solution { //遞迴的記憶化輔助 vector private： int dfp（vector //結束條件 //i，j代表從哪個點一直向下的路徑之和 //下面的條件是i已經超過最底端，所以路徑和返回0 if（i==triangle。size（））return 0； if （mem［i］［j］ ！= 0） { return mem［i］［j］； } //等價關係 return mem［i］［j］=min（dfp（triangle，i+1，j），dfp（triangle，i+1，j+1））+triangle［i］［j］； } public： int minimumTotal（vector int n = triangle。size（）； //對輔助容器的初始化，初始化後二維陣列的空間值自動賦值為0 mem=vector return dfp（triangle，0，0）； } }； 3.動態最佳化 定義二維 dp 陣列，將解法二中「自頂向下的遞迴」改為「自底向上的遞推」 class Solution { public： int minimumTotal（vector int n = triangle。size（）； //對輔助容器的初始化，初始化後二維陣列的空間值自動賦值為0 vector //把每一個位置從底到該處的最小路徑之和都算出來 for （int i = n - 1； i >= 0； i——） { for （int j = 0； j <= i； j++） { dp［i］［j］ = min（dp［i + 1］［j］， dp［i + 1］［j + 1］） + triangle［i］［j］； } } return dp［0］［0］； } }； 4.空間最佳化 3的解法把三角形每一個位置從下到上的路徑之和都搞了出來，其實沒必要，因為我們只要求從下到最頂點的路徑之和，所以只需要用一行陣列儲存前一層的路徑之和讓後一層用就可以，這樣就更加節省空間。 class Solution { public： int minimumTotal（vector int n = triangle。size（）； vector for （int i = n - 1； i >= 0； i——） { for （int j = 0； j <= i； j++） { dp［j］ = min（dp［j］， dp［j + 1］） + triangle［i］［j］； } } return dp［0］； } }； 五、求左上到右下的最小路徑和（Leetcode64） 給定一個包含非負整數的 m x n 網格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。 說明：每次只能向下或者向右移動一步。 示例 1： 輸入：grid = ［［1，3，1］，［1，5，1］，［4，2，1］］ 輸出：7 解釋：因為路徑 1→3→1→1→1 的總和最小。 示例 2： 輸入：grid = ［［1，2，3］，［4，5，6］］ 輸出：12 1.路徑規劃的方法 最主要是的搞清楚往臨時容器中放的是什麼，一次性迴圈放和分開放都可以！ class Solution { public： int minPathSum（vector int m=grid。size（），n=grid［0］。size（）； if（m==0 && n==0）return 0； //對輔助容器的初始化，初始化後二維陣列的空間值自動賦值為0 vector //int dp［m］［n］； //容器或陣列兩個都可以 dp［0］［0］=grid［0］［0］； // 第1行 計算 //第一行初始化 //注意後面是加grid［］［］！ for（int i=1； i dp［0］［i］=dp［0］［i-1］+grid［0］［i］； } //第一列的初始化 for（int j=1； j dp［j］［0］=dp［j-1］［0］+grid［j］［0］； } //把不是第一行第一列位置從起始處到該位置的和算出來初始化 for （int i = 1； i for （int j = 1； j dp［i］［j］ = min（dp［i - 1］［j］， dp［i］［j - 1］） +grid［i］［j］； } } return dp［m-1］［n-1］； } }； 2.進行空間最佳化 想不到想不到 不知道這種二維變一維的空間最佳化大佬們是怎樣想到的，反正我想不到！ class Solution { public： int minPathSum（vector int rows = grid。size（）； int cols = grid［0］。size（）； vector for （int i = 1； i < cols； ++i） dp［i］ = grid［0］［i］ + dp［i - 1］； for （int i = 1； i < rows； ++i） { dp［0］ += grid［i］［0］； for （int j = 1； j < cols； ++j） { dp［j］ = grid［i］［j］ + min（dp［j］， dp［j - 1］）； } } return dp［cols-1］； } }； 個人在大學時習慣於根據決策推進方向可化分為向前和向後兩類。 官方影片講解針對樣例給出了由後向前推進的解析，並給出了簡化dp陣列為一維的方法。本文以一維dp陣列為解題基礎透過向前推進決策的方法給與此題解答。 本文將解決此題的方法概括為“陣列降維，逐行更新” 一。陣列降維 開闢一個長度等於原二維grid陣列列長（設為cols）的一維陣列（vector dp（cols， grid［0］［0］）） 動態規劃問題又可以理解為多段決策最優問題，那麼dp［i］表示在前面i-1步已做出最優決策的前提下第i步做出的決策，並且使得前i步得到的收益最大（本題中指路徑最短）。 值得提出的是，雖然題目中規定了每個點只能向下或者向右移動，但對於第一行的任意點來說，沒有上一行的點會向下移動到該位置。由此對於第一行建立以下等式 dp［i］ = grid［0］［i］ + dp［i - 1］； （1） 以題幹給出的示例為例：遍歷第一行以後 dp陣列的值為{1， 4， 5} 二。逐行更新 設想我們從第二行開始，每一行的每一個點都可以由上邊的點向下移動經過。 對於第i行第j列的點（i > 1）逐行遍歷至該點時，有兩種情況 （1）對於每行的第一個點只有他上邊的點向下移動才可以經過該點 （2）剩下的點都可以由他上邊的點向下移動或左邊的點向右移動到達 對於第一類點，我們遍歷到新一行時，由於該點只能由其他點向下移動到達我們就可以根據前一行的dp［0］來更新該點的決策值 dp［0］ += grid［i］［0］ （2） 對於第二類點，我們可以得到如下等式 dp［j］ = grid［i］［j］ + min（dp［j-1］，dp［j］） 等式右邊dp［j］代表當前點上一行對應位置點的決策收益值 dp［j-1］代表當前位置左側點的決策收益值。 大佬詳解連結：動態規劃的最佳化 其他習題： 另外還有力扣的279題，91題，64題，63題。