1. 介紹

• 動態規劃 (Dynamic Programming, DP)
• 保存子問題, 避免重復計算
• 關鍵是: 找到轉移方程, 確定邊界條件, 明確dp陣列含義
• 比如我們熟悉的斐波那契數列, 其實dp跟遞回是一樣的, 只是因為遞回占用時間和空間較大, 所以盡可能使用dp解題, 事半功倍.

int feiB(int n){
	if(n<=1) return n;
	vector<int>dp(n+1, 0); //多出來一個, 因為feiB(3) = 2
	dp[0]=0, dp[1]=1;  // 邊界條件
	for(int i=2; i<=n; i++){ 
		dp[i] = dp[i-1]+dp[i-2]; // 轉移方程
	}
	cout<<n<<"的結果是"<<dp[n]<<endl;
	return dp[n];
}

2. 子序列問題

解題思路:

1. 思考問題能不能轉化成樹的形式
2. 思考樹是不是自底向上求取結果
3. 根據這個樹, 確定自底向上的關系式, 比如上層節點A = 下層節點(A1+A2)
4. 具體操作見下面的示例圖解

這部分問題, 筆試面試的時候出的特別多, 因為這部分問題如果有思路, 很快就能確定解決方案, 并且代碼量不多, 只需要理解動態規劃就會很好寫, 具體的題目見下面, 對于前兩個題兩個題太重要了, 一定要牢牢掌握住, 為后面的筆試面試奠基牢固的基礎, 因為第三個題往后都是這兩個題的延伸延伸延伸.

1143.最長公共子序列

給定兩個字串 text1 和 text2，回傳這兩個字串的最長 公共子序列 的長度，如果不存在 公共子序列 ，回傳 0 ，

輸入：text1 = "abcde", text2 = "ace" 
輸出：3  
解釋：最長公共子序列是 "ace" ，它的長度為 3 ，
輸入：text1 = "abc", text2 = "abc"
輸出：3
解釋：最長公共子序列是 "abc" ，它的長度為 3 ，
輸入：text1 = "abc", text2 = "def"
輸出：0
解釋：兩個字串沒有公共子序列，回傳 0 ，

int longestCommonSubsequence(string text1, string text2) {
	int m=text1.size();
	int n=text2.size();
	vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
	//print_vv(dp);
	for(int i=1; i<=m; i++){
		for (int j = 1; j<=n; ++j) {
			if(text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
		}
	}
	//print_vv(dp);
	return dp[m+1][n+1];
}

string text1="abcde";
string text2="ace";
int a = longestCommonSubsequence(text1, text2);

300.最長遞增子序列

給你一個整數陣列 nums ，找到其中最長嚴格遞增子序列的長度，
子序列是由陣列派生而來的序列，洗掉（或不洗掉）陣列中的元素而不改變其余元素的順序，例如，[3,6,2,7] 是陣列 [0,3,1,6,2,2,7] 的子序列，

輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 ，
輸入：nums = [0,1,0,3,2,3]
輸出：4

由上圖可知, 比如第4個位置對應的最長遞增子序列, 其結果跟前三個位置都相關

class Solution {
public:
    // 可能是動態規劃, 從底層往上層走, 發現4跟123有關, 即4是123其中最大值加一如果4大于123
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n=nums.size();
        
        vector<int> dp(n, 1); // 只要陣列不空, 遞增子序列最差也是1
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        // print_v(dp);
        return *max_element(dp.begin(), dp.end());
    }
};

2.1 最長遞增子序列應用

354.俄羅斯套娃

17.08 馬戲團人塔

做完上面那倆題之后, 在做這個題, 如果這個題還不會做, 請重復做上面那倆題, 直到不看答案, 能夠解決這個題, 算成功

給你一個二維整數陣列 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 個信封的寬度和高度，當另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進另一個信封里，如同俄羅斯套娃一樣，
請計算 最多能有多少個 信封能組成一組“俄羅斯套娃”信封（即可以把一個信封放到另一個信封里面），
注意：不允許旋轉信封，

輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出：3
解釋：最多信封的個數為 3, 組合為: [2,3] => [5,4] => [6,7]，

輸入：envelopes = [[1,1],[1,1],[1,1]]
輸出：1

思考:
首先想一下, 如果說把這個二維變成一維, 是不是就是最長遞增子序列
只不過這個題增加了一個維度, 那我們思考一下, 能不能先對一側進行排序, 然后在另一側計算最長遞增子序列呢???
答案很顯然是可以的

輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
先對list的第一列排序, [[2,3], [5,4], [6,4], [6,7]]
然后在對第一列相等的, 倒敘排序第二列 , [[2,3], [5,4], [6,7], [6,4]]
然后在看[3,4,7,4]的最長遞增子序列即可
思考: 第一個排序可以理解, 為何倒敘排列第二列???
參考 [[2,3], [5,4], [5,8], [6,7], [6,6], [6,3]]
這里如果[[5,4], [5,8]]是順序, 則[3,4,8,7] 最長子序列是3, 也就是吧[5,4] 包金來了, 
但是[[6,7], [6,6], [6,3]], [3,4,8,7,6,3], 就不會把[[6,6], [6,3]]包進來;

class Solution {
public:
    struct myCompare{
        bool operator()(vector<int> &a, vector<int> &b){
            // 先對第一列進行排序, 如果第一列有相等的比如[2,1], [2,3] 在對第二列進行排列成[2,3],[2,1],
            return (a[0] < b[0]) || (a[0]==b[0] && a[1] > b[1]);
        }
    };

    int maxEnvelopes(vector<vector<int>> &nums){
        if(nums.empty()) return 0;
        int n=nums.size();
        sort(nums.begin(), nums.end(), myCompare()); // 按要求排序
        vector<int>dp (n, 1);
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                if(nums[i][1] > nums[j][1]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
        
    }
};

3. 路徑問題

64. 最短路徑和

給定一個包含非負整數的m x n網格grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小，
說明：每次只能向下或者向右移動一步，

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因為路徑 1→3→1→1→1 的總和最小，
輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

思考:

1. 最短路徑和有點像貪婪演算法的意思
2. 從左上角開始, 找右/下最小值走, 但是顯然不對, 就如上圖所示
3. 但是可以想一下, 當前值只跟左/上兩個有關系, 所以最終dp[i][j]就可表示為從(0,0)->(i,j)的對小花費

dp[i][j] = min(dp(i-1, j) , dp(i, j-1)) + nums[i][j];
邊界條件就是dp的第一列和第一行是nums的累加

class Solution {
public:
    int minPathSum(vector<vector<int>>& nums) {
        if(nums.empty() || nums[0].empty()) return 0;
        int m = nums.size(), n = nums[0].size();

        vector<vector<int>> dp(m, vector<int>(n));

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 && j==0) dp[0][0] = nums[0][0];
                else if(i==0) dp[i][j] = dp[i][j-1]+nums[i][j];
                else if(j==0) dp[i][j] = dp[i-1][j]+nums[i][j];
                else dp[i][j] = min(dp[i-1][j], dp[i][j-1])+nums[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

221. 最大正方形

在一個由 ‘0’ 和 ‘1’ 組成的二維矩陣內，找到只包含 ‘1’ 的最大正方形，并回傳其面積，

輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出：4

1. dp[i][j]表示從i,j到左上的正方形邊長

class Solution {
public:
    int min_3(int &a, int &b, int &c){
        return min(min(a, b),c);
    }

    /*
    1. dp[i][j] 表示從(i,j)到 左上方 最大的正方形的邊長
    2. dp[i][j] = min(左, 上, 左對角) + 1
    */
    int maximalSquare(vector<vector<char>>& nums) {
        if(nums.empty() || nums[0].empty()) return 0;
        int m=nums.size(), n=nums[0].size();

        int ans=0;
        vector<vector<int>>dp(m, vector<int>(n,0));
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 || j==0){
                    dp[i][j] = nums[i][j] - '0';
                }
                else if(nums[i][j] == '1'){
                    dp[i][j] = min_3(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans*ans;
    }
};

4. 背包問題

• 組合優化的 NP 完全問題

• 有 N 個物品和容量為 W 的背包，每個物品都有自己的體積 w 和價值 v，求拿哪些物品可以使得背包所裝下物品的總價值最大，限定每種物品只能選擇 0 個或 1 個，則問題稱為 0-1 背包問題；如果不限定每種物品的數量，則問題稱為無界背包問題或完全背包問題，

• 對于背包問題動態方程,

• 設dp[i,j]表示第i物品容量為j的位置背包的價值最多
  因此可以考慮這樣求解
  i物品放入背包, 此時背包減去i物品重量后,剩余空間是j-w[i], 所以找到上一個物品的j-w[i]

01背包問題

• 這里需要注意的是: 邊界條件
• 跳轉關系見圖示
  

/*
1. dp含義: dp[i][j] 表示任取0-i的物品放到容量為j的背包里面的最大值
2. 遞推公式: dp[i][j]取決于當前物品
             i不放 dp[i][j]=dp[i-1][j] 就跟上一個物品放不放一致
             i放dp[i][j]=dp[i-1][j-weight[i]] + value[i] 空間減掉當前物品空間, 價值加上當前拿物品的價值,
3. 初始化: 第一行和第一列
4. 回圈順序: 
*/
int bakage_01(vector<int> weight, vector<int> value, int maxW){
    vector<vector<int>> dp(weight.size(), vector<int>(maxW+1, 0));
    for(int i=0; i<weight.size(); i++){ //物品
        for(int j=1; j<=maxW; j++){ // 背包容積
            if(i == 0 && weight[0] <= j) { // 第一行, 第一個物品如果重量大于背包容量, 則為value0
                dp[0][j] = value[0];
            }else if(j < weight[i]){ // 背包容積小
                dp[i][j] = dp[i-1][j]; //只跟上一個物品相關
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
            }
        }
    }
    print_vv(dp);
    return dp[weight.size()-1][maxW];
}

• 空間壓縮
  因為上面dp[i]行值只與i-1相關, 所以只需要定義一維空間, 一行一行進行填寫, 最后完成dp[j]即為所求

// 空間壓縮
int knapsack_optimize(vector<int> weights, vector<int> values, int N, int W) {
	vector<int>dp(W+1, 0);
	int w,v;
	for(int i=1; i<=N; i++){
		w=weights[i-1], v=values[i-1];
		for(int j = W; j>=w; j--){ // 這里大于w是為了去除沒用的, 也可以為j>0
			dp[j] = max(dp[j], dp[j-w]+v);
		}
		print_v(dp);
	}
	return dp[W];
}

01背包問題的應用 是否可以一個陣列分成和相等的兩部分

416. 是否可以一個陣列分成和相等的兩部分

給你一個 只包含正整數 的 非空 陣列 nums ，請你判斷是否可以將這個陣列分割成兩個子集，使得兩個子集的元素和相等，

輸入：nums = [1,5,11,5]
輸出：true
解釋：陣列可以分割成 [1, 5, 5] 和 [11] ，
輸入：nums = [1,2,3,5]
輸出：false
解釋：陣列不能分割成兩個元素和相等的子集，

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum & 1) return false; 
        int target = sum/2;
        if(*max_element(nums.begin(), nums.end()) > target) return false;

        vector<vector<bool>> dp(nums.size(), vector<bool>(target+1, false));
        dp[0][nums[0]] = true; // 第一行的第nums[0]列為true 初始化, 因為一個物品放到背包中正好等于背包容積
        for(int i=1; i<nums.size(); i++){
            for(int j=1; j<=target; j++){
                if(nums[i] > j) dp[i][j] = dp[i-1][j]; // 當前物體容積太大, 不取, 則跟上面的一樣
                else if(nums[i] == j) dp[i][j] = true; // 當前值正好等于背包容積
                else{
                    // 當前值小于背包容積, 放進去的話是dp[i-1][j-nums[i]], 不放進去的話是dp[i-1][j]
                    dp[i][j] = dp[i-1][j-nums[i]] | dp[i-1][j]; 
                }
            }
        }
        return dp[nums.size()-1][target];
    }
};

4.2 完全背包問題

int knapsack_fully(vector<int> weights, vector<int> values, int N, int W) {
	std::vector<std::vector<int>> dp(N+1, std::vector<int>(W+1, 0));
	int w,v;
	for(int i=1; i<=N; i++){
		w=weights[i-1], v=values[i-1];
		for(int j = 1; j<=W; j++){
			if(j>=w){  
				dp[i][j] = max(dp[i-1][j], v+dp[i][j-w]);
			}else{
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	print_vv(dp);
	return dp[N][W];
}

5. 分割問題