前言

動態規劃（DP）的定義：動態規劃是分治思想的延伸，通俗一點來說就是大事化小，小事化無的藝術，
動態規劃具備了以下三個特點：

把原來的問題分解成了幾個相似的子問題，
所有的子問題都只需要解決一次，
儲存子問題的解

并且我們通常從以下的四個角度來出發（重要）

狀態定義
狀態間的轉移方程定義
狀態的初始化
回傳結果

一、為何要使用動態規劃？

我們首先看這樣一道題目

在這里插入圖片描述

斐波那契

點擊鏈接跳轉：斐波那契數列

同學們可能在初始學習C語言，學到遞回的時候肯定少不了這道經典的題目,大家通常也都是用遞回的方式去完成，但是我們發現一點，當我們用遞回實作斐波那契數的演算法是2^n的時間復雜度，數字給的大的時候就求不出來了，這時我們就會用到動態規劃的思想
廢話不多說，現在我們來看看按照我們上面給的邏輯如何用我們的四個步驟完成這道題目

狀態的定義：求F(n)的值
狀態方程的轉換：F(n)=F(n-1)+F(n-2)
初始化： F（0） =0；F(1)=1
回傳結果：F（n）

C++實作：
class Solution {
public:
    int Fibonacci(int n) {
        vector<int> v;
        //初始化
        v.push_back(0);
        v.push_back(1);
        //狀態的轉移方程
        for(int i=2;i<=n;i++)
        {
           int ret  = v[i - 1] + v[i - 2];
            v.push_back(ret);
        }
        //回傳結果
        
        return v[n];
    }
};

二、最大連續的子陣列和

最大連續的子陣列和
在這里插入圖片描述

int FindGreatestSumOfSubArray(vector<int> array)

這里我們就該思考他的狀態如何定義，假設我們這里用前i個元素的陣列的最大和作為狀態的定義，我們會發現，我們無法利用前一個狀態，做出變化轉換到下一個狀態，
我們這里的狀態定義：以第i個元素為結尾的最大的子陣列和
原因：我們在新增元素進去時，我們就可以根據新增元素是否需要加入進去并且保持是一個連續的子陣列和
狀態遞推：F[i] = max(F[i-1]+array[i-1],array[i-1]);意思即上一個最大值是否加入當前值與該元素本身比較后將大的放入F（i）中
結果：回傳我們陣列當中最大的值即是在這個陣列當中的最大的子陣列和

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int sz = array.size();
        vector<int> F(sz+1);
        //初始化
        F[1] = array[0];
        for(int i =2;i<=sz;i++)
        {
            //遞推方程：以i結尾的子陣列最大和
            F[i] = max(F[i-1]+array[i-1],array[i-1]);
        }
        int maxI = F[1];
        for(int i =2 ;i<= sz;++i)
        {
            maxI = max(F[i],maxI);
        }
        return maxI;
    }
};

三、LC12 拆分詞句

LC12 拆分詞句

bool wordBreak(string s, unordered_set<string> &dict)

分析題意：就是要我們在給定的字串中判斷是否能將字串分割成字典dict中能找到的值
狀態定義：前i個字符能否在dict中查找到
**狀態轉換：**這里先解釋一點，狀態的轉換不一定是一個等式，比如在這個地方，定義為，j<i && F(j) && (j+1,i) 為dict中單詞，解釋一下，就是我們要利用前面j個字符的狀態，當前面的j個字符為在dict中能中能找到，即F（j）為真，我們只需要在判斷(j+1，i)這個區間也是在dict當中能查找的字串就能保證整體為真了！（這里的F(j)是兩個或多個字符組成的都沒關系，在dict當中能找到就表明他是真）
初始化：我們這里的起始狀態可以給一個"",表示空串，在這個的基礎上的狀態轉換方程表示的是，字串整體能在dict中查找到，即將F[0] 置成ture

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
// 前j個字符能在dict中查找
// 狀態方程：j<i && f[j] && [j+1,i]組成字符
// 特殊情況：第一個字符
// F[0] ture, F[1] --要把F[0]弄成輔助狀態，這樣表示前j個字符為整體的時候在dict中能查找
        int n = s.size();
        vector<bool> canBreak(n+1 ,false);//前i個字符 -- 映射下標位置
        canBreak[0]=true;//這個是輔助狀態
        for(int i= 1; i <= n;i++)//處理第一個到第n個字符
        {
            for(int j =i-1 ; j >= 0 ;j--)
            {
               if(canBreak[j] && dict.find(s.substr(j,i-j))!=dict.end())// 狀態方程：j<i && f[j] && [j+1,i]組成字符
               {
                   canBreak[i] =true;
               }
            }
        }
        return canBreak[n];
    }
};

這題的狀態轉換其實就沒有之前的兩道題好想了，但是我們在思考的時候能夠想到狀態的轉換問題其實就已經解決了，所以很多時候都是只差臨門一腳

四、三角形

跳轉鏈接：三角形
在這里插入圖片描述

int minimumTotal(vector<vector<int> > &triangle)

像題目所給的這種我們很容易就能判斷出來結果，但如果我們將第三行的70改成1的話我們答案會如何呢
在這里插入圖片描述

下圖演示的例子：
初始化的例子：

分析：觀察上圖的兩張表，我們可以看出，要求出從上到下的最小和，并且一次移動只能移動到從(i,j)–> (i+1,j),(i+1,j+1) ，很明顯我們不能就直接選擇下一行的最小值，所以我們要個二維陣列去保存所有的子陣列的和F(i,j)
狀態定義：到第i行的最小值
狀態轉換：以圖中的50分析：因為當前行的大小是由 F(i,j) -->
min(F(i-1,j),F(i-1,j-1))+(i,j)，即我們可以保存從上面下來的所有情況的最小和，例如：50這個位置就是從20 -->30–>50，所以50對應的二維陣列存放這100-- 這樣說應該就能理解了
初始化：可以從上面的圖看出，當 j== 0時，即第一列和當 i==j時，對角線他們的可能只能是從固定位置下來的，所以我們初始化的時候先將這些值置成對應的值
解題：我的解題當中所用的是直接在他們給我們的二維陣列triangle中更新，因為我們遍歷陣列的時候剛好可以就將值更新好放回去

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
//         直接用triangle二維陣列記錄當前位置的最小值

// 初始化第0列的應該加上上一行的值加上這一行的值，i==j的就可以上一(i-1,j-1)的值加上當前值，其他的位置就可以是上一行的和上一行上一列的最小值加上當前值
        int x =triangle.size();
        for(int i =1;i<x;i++)
        {
            for(int j=0;j<i+1;j++)
            {
                if(j==0)
                    triangle[i][j]=triangle[i-1][j]+triangle[i][j];
                else if(i == j)
                {
                    triangle[i][j]=triangle[i-1][j-1]+triangle[i][j];
                }
                else
                {
                    triangle[i][j]=triangle[i][j]+min(triangle[i-1][j-1],triangle[i-1][j]);
                }
            }
        }
        int y =triangle[x-1].size();
        int minret= triangle[x-1][0];
        for(int i=1;i<y;++i)
        {
            minret = min(minret,triangle[x-1][i]);
        }
        return minret;
    }
};

五、LC88 求路徑

LC88 求路徑
在這里插入圖片描述

決議：這道題的題意非常簡單，從起點到終點求路徑，且每次只能往下或者往右

根據上圖：其實每個點路徑和是上一行和左一列到該位置的路徑和相加，所以我們用一個二維陣列去保存子答案的結果
狀態定義: 從(0,0)到（i，j）的路徑數
狀態轉換：F(i,j) =F(i-1,j)+F(i,j-1) – 即每個點的路徑和個數為上一行和左邊一列的和相加
初始化：觀察到第一行和第一列，他們都只有一種可能性，一直往右走，和一直往下走，所以初始化的時候我們將他們全部置成1；
回傳：F（m-1，n-1）

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        //狀態轉換 --(i,j)是(i-1,j)與(i,j-1)走多一步得到的
        vector<vector<int>> retArr(m,vector<int>(n,0));
        retArr[0][0]=1;
        for(int i =1;i<m;++i)
        {
            
            retArr[i][0]=1;//處理第一列
        }
        for(int i =1;i<n;++i)
        {
            retArr[0][i]=1;//處理第一行
        }
        for(int i = 1;i<m;++i)
        {
            for(int j =1;j<n;++j)
            {
                retArr[i][j] =retArr[i-1][j]+retArr[i][j-1];
            }
        }
        return retArr[m-1][n-1];
    }
};

六、LC87 求路徑 ii

LC87 求路徑 ii
在這里插入圖片描述

分析：比起上一題這里就是添加了障礙，在有障礙的地方我們置成路徑和為0的話，那么結論每個點路徑和是上一行和左一列到該位置的路徑和相加，所以我們用一個二維陣列去保存子答案的結果在這里也是適用的

狀態定義: 從(0,0)到（i，j）的路徑數
狀態轉換：F(i,j) =F(i-1,j)+F(i,j-1) – 即每個點的路徑和個數為上一行和左邊一列的和相加
初始化：初始化我們將第一行，第一列有路障的后面置0，并且(0,0)如果是有路障或者終點處有路障直接就回傳0
技巧： 我們可以將我們的二維陣列提前置成0，這樣初始化遍歷的時候我們break跳出回圈相當于也將后面的初始化完成了，具體看下面的代碼吧！！！

class Solution {
public:
    /**
     * 
     * @param obstacleGrid int整型vector<vector<>> 
     * @return int整型
     */
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
        // write code here
//         到(i,j)！=1的時候就有
// 也等于（i-1,j） 和（i,j-1）
// 初始化的時候0,0 為1直接回傳
// 初始化之后我們將有障礙的都置成0，這樣我們就可以套用上題的思路
        if(obstacleGrid.empty())
            return 0;
        int x =obstacleGrid.size();
        int y =obstacleGrid[0].size();
        if(obstacleGrid[0][0]||obstacleGrid[x-1][y-1])
            return 0;
        vector<vector<int>> retArr(x,vector<int>(y,0));//置成0方便后續我們操作
        for(int i=0;i<x;i++)
        {
            if(obstacleGrid[i][0] == 1)
                break;//有障礙的話我們就直接退出
            retArr[i][0]=1;
        }
        for(int i=0;i<y;i++)
        {
            if(obstacleGrid[0][i] == 1)
                break;
            retArr[0][i]=1;
        }
        for(int i =1;i<x;i++)
        {
            for(int j =1;j<y;j++)
            {
                if(obstacleGrid[i][j]==0)
                retArr[i][j] = retArr[i-1][j]+retArr[i][j-1];
                else
                retArr[i][j]= 0;
            }
        }
        return retArr[x-1][y-1];
    }
};

相似的題目：LC86 帶權值的最小路徑和，自己也動手試試吧

七、背包問題

背包問題

> 這里是參考

如果看到這題的時候，你已經在能夠自己推導這道題的狀態定義和轉換方程，再來聽聽我講的，那么這道題可能會比較容易吸收

狀態：
F(i, j): 前i個物品放入大小為j的背包中所獲得的最大價值，如果不將j置成變數的話前i個物品放入背包中所獲得的最大價值，是沒有辦法判斷當前背包大小是否夠放當前物品的 – 難
狀態遞推：對于第i個商品，有一種例外，裝不下，兩種選擇，放或者不放
如果裝不下：此時的價值與前i-1個的價值是一樣的
F(i,j) = F(i-1,j)，如果可以裝入：需要在兩種選擇中找最大的
F(i, j) =max(F[i-1][j-A[i-1]]+V[i-1],F[i-1][j])
F(i-1,j): 表示不把第i個物品放入背包中，所以它的價值就是前i-1個物品放入大小為j的背包的最大價值
F(i-1, j - A[i]) + V[i]：表示把第i個物品放入背包中，價值在該物品價值的基礎上增加V[i],但是需要騰出j - A[i]的大小放第i個商品

我們以題目的情況進行分析
初始化：在這里插入圖片描述