509. 斐波那契數

力扣題目鏈接

題目：斐波那契數（通常用F(n)表示）形成的序列稱為斐波那契數列 。該數列由0和1開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定 n ，請計算 F(n) 。

思路：數據量不大，遞推一下

通過代碼：

class Solution {
public:int fib(int n) {if(n < 2)return n;int a = 0, b = 1, c;for(int i = 0; i < n - 1; i++){c = a + b;a = b;b = c;}return c;}
};

70. 爬樓梯

力扣題目鏈接

假設你正在爬樓梯。需要n階你才能到達樓頂。

每次你可以爬1或2個臺階。你有多少種不同的方法可以爬到樓頂呢？

思路：每一級臺階都可以由前兩個臺階走到，前一個臺階跨一步，前兩個臺階跨兩步

通過代碼：

class Solution {
public:int climbStairs(int n) {vector<int> steps(46, 0);steps[1] = 1;steps[2] = 2;for(int i = 3; i <= n; i++)steps[i] = steps[i - 1] + steps[i - 2];return steps[n];}
};

746. 使用最小花費爬樓梯

力扣題目鏈接

題目：給你一個整數數組cost ，其中cost[i] 是從樓梯第i個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。

你可以選擇從下標為0 或下標為1的臺階開始爬樓梯。

請你計算并返回達到樓梯頂部的最低花費。

思路：可以有兩個途徑得到dp[i]，一個是dp[i-1]一個是dp[i-2]。dp[i-1]跳到dp[i]需要花費dp[i - 1] + cost[i - 1]。dp[i-2]跳到dp[i]需要花費dp[i-2] + cost[i-2]。

那么究竟是選從dp[i - 1]跳還是從dp[i - 2]跳呢？一定是選最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

通過代碼：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1, 0);dp[0] = 0;dp[1] = 0;for(int i = 2; i <= n; i++)dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);return dp[n];}
};

62.不同路徑

力扣題目鏈接

題目：一個機器人位于一個m x n網格的左上角（起始點在下圖中標記為“Start”）。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。問總共有多少條不同的路徑？

思路：每個網格只能從其上方或左邊過來，因此其路徑數為其上方和左側之和。

通過代碼：

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int> (n));for(int i = 0; i < n; i++)dp[0][i] = 1;for(int i = 0; i < m; i++)dp[i][0] = 1;for(int i = 1; i < m; i++)for(int j = 1; j < n; j++)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[m - 1][n - 1];}
};

63. 不同路徑 II

力扣題目鏈接

題目：一個機器人位于一個m x n網格的左上角（起始點在下圖中標記為“Start”）。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish”）?，F(xiàn)在考慮網格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？網格中的障礙物和空位置分別用 1 和 0 來表示。

思路：和前一題類似，只不過需要處理一下有障礙的情況。狀態(tài)轉移的時候有障礙的格子賦0即可，初始化的時候一旦遇到障礙就要結束。

通過代碼：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(), n = obstacleGrid[0].size();vector<vector<int>> dp(m, vector<int> (n, 0));if(obstacleGrid[0][0])dp[0][0] = 0;elsedp[0][0] = 1;for(int i = 1; i < n && obstacleGrid[0][i] == 0; i++)dp[0][i] = dp[0][i - 1];for(int i = 1; i < m && obstacleGrid[i][0] == 0; i++)dp[i][0] = dp[i - 1][0];for(int i = 1; i < m; i++)for(int j = 1; j < n; j++){if(obstacleGrid[i][j])dp[i][j] = 0;elsedp[i][j] = dp[i -1][j] + dp[i][j - 1];}return dp[m - 1][n - 1];}
};

343. 整數拆分

力扣題目鏈接

題目：給定一個正整數n，將其拆分為k個正整數的和（k >= 2），并使這些整數的乘積最大化。返回你可以獲得的最大乘積 。

思路：dp[i]表示i的最大乘積。有兩種渠道可以得到dp[i]，一種是j*(i - j)，另一種是dp[j] * (i - j)。前者代表不對j拆分，后者代表對j進行拆分，由于j差分的最大乘積在之前的遍歷已經算出來了，所以直接用dp[j]即可。在這種渠道選一個大的即可，最后在整個遍歷過程中取一個大的。

通過代碼：

class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[1] = 1;dp[2] = 1;for(int i = 3; i <= n; i++){dp[i] = dp[i - 1];for(int j = i - 2; j >= 1; j--)dp[i] = max(dp[i], max(dp[j], j) * (i - j));}return dp[n];}
};

96.不同的二叉搜索樹

力扣題目鏈接

題目：給你一個整數n，求恰由n個節(jié)點組成且節(jié)點值從1到n互不相同的二叉搜索樹有多少種？返回滿足題意的二叉搜索樹的種數。

思路：dp[i]表示i個節(jié)點組成的樹的種數。以j為根節(jié)點，則前j-1個節(jié)點必在其左子樹，其種數為dp[j - 1]；后i-j個節(jié)點必在其右子樹，其種數為dp[i - j]。所以，以j為根節(jié)點的種數合計為dp[j - 1] * dp[i - j]。dp[i]的值對以1到i為根節(jié)點的種數求和即可。

通過代碼：

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++)for(int j = 1; j <= i; j++)dp[i] += dp[j - 1] * dp[i - j];return dp[n];}
};

416. 分割等和子集

力扣題目鏈接

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

思路：首先排除一些明顯無法分割的情況：元素數量小于2、總和為奇數、最大元素超過總和的一半。將問題轉化為01背包，取一些數使得其和為target。定義dp數組，dp[i][j]表示能否在下標為0到i的范圍選一些數使得和為j。對于新擴展進來的數nums[i]，我們有兩種選擇，一是不選，那么結果就為dp[i-1][j]，二是選，結果就為dp[i-1][j-nums[i]]。只要這兩個結果中的一個為true，那么dp[i][j]就為true。

通過代碼：

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size(), sum = 0, maxn = 0;if(n < 2)return false;for(int num : nums){sum += num;maxn = max(maxn, num);}if(sum % 2 == 1)return false;int target = sum / 2;if(maxn > target)return false;vector<bool> dp(target + 1, false);dp[0] = true;dp[nums[0]] = true;for(int i = 1; i < n; i++)for(int j = target; j >= nums[i]; j--)dp[j] = dp[j] || dp[j - nums[i]];return dp[target];}
};

1049.最后一塊石頭的重量II

力扣題目鏈接

題目：有一堆石頭，用整數數組stones表示。其中stones[i]表示第i塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設石頭的重量分別為 x和y，且x <= y。那么粉碎的可能結果如下：

• 如果x == y，那么兩塊石頭都會被完全粉碎；
• 如果x != y，那么重量為x的石頭將會完全粉碎，而重量為y的石頭新重量為y-x。

最后，最多只會剩下一塊石頭。返回此石頭最小的可能重量 。如果沒有石頭剩下，就返回0。

思路：考慮將石頭分成兩堆，每次從兩堆中各取一個石頭粉碎。小的那個石頭會完全粉碎，大的石頭會減去小石頭的重量。因此每次粉碎對于整個堆的總和來說都是減去相同的重量。由此，問題轉化為了將石頭分成重量盡可能接近的兩堆。這就類似于上一題了。分成重量盡可能接近的兩堆，又可以轉化為選取一些石頭，使得這些石頭的重量接近總重的一半。所以背包容量就是總重的一半。石頭的價值就是石頭的重量，價值越大越好就是重量越接近背包上限越好。而背包上限就是總重的一半，因此就能找到最接近總重一半的石頭堆。

通過代碼：

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for(int num : stones)sum += num;int target = sum / 2 + 1;vector<int> dp(target, 0);for(int i = 0; i < stones.size(); i++)for(int j = target - 1; j >= stones[i]; j--)dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);return sum - dp[target - 1] - dp[target - 1];}
};

494.目標和

力扣題目鏈接

題目：給你一個非負整數數組nums和一個整數target 。向數組中的每個整數前添加'+'或'-'，然后串聯(lián)起所有整數，可以構造一個表達式 ：

• 例如，nums = [2, 1]，可以在2之前添加'+'，在1之前添加 '-' ，然后串聯(lián)起來得到表達式"+2-1" 。

返回可以通過上述方法構造的、運算結果等于target的不同表達式的數目。

思路：難在如何轉化為背包問題。一旦找到轉化的思路，就容易了。假設加負號的整數的和為neg，那么加正號的整數的和為sum-neg（sum為nums的總和）。根據題意有(sum-neg)-neg=target，即sum-2*neg=target，由于sum和target都是定值，因此也能求出neg為(sum-target)/2。由于是非負整數數組，所以neg肯定也是非負整數，不是的話就是無解。于是問題就可以轉化為在nums中選一些數使得和為neg，求幾種選法，從而轉化為了01背包問題。后面不再贅述。

通過代碼：

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int num : nums)sum += num;if(sum - target < 0 || (sum - target) % 2)return 0;int neg = (sum - target) / 2;vector<int> dp(neg + 1, 0);dp[0] = 1;for(int i = 0; i < nums.size(); i++)for(int j = neg; j >= nums[i]; j--)dp[j] = dp[j] + dp[j - nums[i]];return dp[neg];}
};

474.一和零

力扣題目鏈接

題目：給你一個二進制字符串數組strs和兩個整數m和n 。請你找出并返回 strs 的最大子集的長度，該子集中最多有m個0和n個1 。

如果x的所有元素也是y的元素，集合x是集合y的子集 。

思路：01背包的影子很容易看出來，就是背包容量有了兩個維度，一個是0的數量，一個是1的數量。換成背包問題的表述就是背包容量為m和n，求能裝的字符串的最大數量。一個字符串中的1的數量和0的數量就是代價，價值就是個數可以+1。如果不壓縮空間的話就要開三維數組，因此這里仍然采用滾動數組。最外層依然是遍歷字符串的個數。里面兩層依次遍歷背包的兩個維度，注意都要從后往前遍歷。

通過代碼：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));for(string s : strs){int ones = count(s.begin(), s.end(), '1');int zeros = s.size() - ones;for(int i = m; i >= zeros; i--)for(int j = n; j >= ones; j--)dp[i][j] = max(dp[i][j], dp[i -zeros][j - ones] + 1);}return dp[m][n];}
};

518.零錢兌換II

力扣題目鏈接

題目：給你一個整數數組coins表示不同面額的硬幣，另給一個整數amount表示總金額。請你計算并返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回0。

假設每一種面額的硬幣有無限個。 題目數據保證結果符合 32 位帶符號整數。

思路：近乎完全背包模板題（參考鏈接）。背包容量為amount，每個硬幣無限數量，硬幣面值就是代價。注意dp[0]一定要為1。

通過代碼：

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for(int i = 0; i < coins.size(); i++)for(int j = coins[i]; j <= amount; j++)dp[j] += dp[j - coins[i]];return dp[amount];}
};

377. 組合總和 Ⅳ

力扣題目鏈接

題目：給你一個由 不同 整數組成的數組nums，和一個目標整數target。請你從nums中找出并返回總和為target的元素組合的個數。

題目數據保證答案符合 32 位整數范圍。

思路：完全背包。把兩個for循環(huán)反過來，就是排列。target（背包）放在外循環(huán)，將nums（物品）放在內循環(huán)，內循環(huán)從前到后遍歷。

通過代碼：

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for(int i = 1; i <= target; i++)for(int j = 0; j < nums.size(); j++){if(i >= nums[j] && dp[i] < INT_MAX - dp[i - nums[j]])dp[i] += dp[i - nums[j]];}return dp[target];}
};

322. 零錢兌換

力扣題目鏈接

題目：給你一個整數數組coins，表示不同面額的硬幣；以及一個整數amount，表示總金額。計算并返回可以湊成總金額所需的最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回-1 。你可以認為每種硬幣的數量是無限的。

思路：典型的完全背包。湊足總額為j - coins[i]的最少個數為dp[j - coins[i]]，那么只需要加上一個錢幣coins[i]，即dp[j - coins[i]] + 1就是dp[j]。所以dp[j]要取所有dp[j - coins[i]] + 1中最小的。

遞推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

注意我初始化都為-1，除了dp[0]=0，遞推的時候還要注意無解的情況。

通過代碼：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, -1);dp[0] = 0;for(int i = 0; i < coins.size(); i++)for(int j = coins[i]; j <= amount; j++){if(dp[j] != -1 && dp[j - coins[i]] != -1)dp[j] = min(dp[j], dp[j - coins[i]] + 1);else if(dp[j] == -1 && dp[j - coins[i]] != -1)dp[j] = dp[j - coins[i]] + 1;} return dp[amount];}
};

279.完全平方數

力扣題目鏈接

題目：給你一個整數n，返回和為n的完全平方數的最少數量 。

完全平方數是一個整數，其值等于另一個整數的平方；換句話說，其值等于一個整數自乘的積。例如，1、4、9 和 16都是完全平方數，而3和11不是。

思路：n的最大值為10000，所以完全平方數的范圍就是1-100的平方。而且都是可以無限使用的，所以就是典型的完全背包。類似于上面一道題，1-100就相當于硬幣面值，n就相當于amount，也就是背包容量。

通過代碼：

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for(int i = 1; i <= 100; i++)for(int j = i * i; j <= n; j++)dp[j] = min(dp[j], dp[j - i * i] + 1);return dp[n];}
};

139.單詞拆分

力扣題目鏈接

題目：給你一個字符串s和一個字符串列表wordDict作為字典。如果可以利用字典中出現(xiàn)的一個或多個單詞拼接出s則返回 true。

注意：不要求字典中出現(xiàn)的單詞全部都使用，并且字典中的單詞可以重復使用。

思路：單詞就是物品，字符串s就是背包，單詞能否組成字符串s，就是問物品能不能把背包裝滿。如果確定dp[j]是true，且 [j, i] 這個區(qū)間的子串出現(xiàn)在字典里，那么dp[i]一定是true（j < i）。

通過代碼：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for(int i = 1; i <= s.size(); i++)for(int j = 0; j < i; j++)	//枚舉字符串就是枚舉起始位置{string word = s.substr(j, i - j);if(wordSet.find(word) != wordSet.end() && dp[j])dp[i] = true;}return dp[s.size()];}
};

198.打家劫舍

力扣題目鏈接

題目：你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你不觸動警報裝置的情況下，一夜之內能夠偷竊到的最高金額。

思路：dp[i]：考慮下標i（包括i）以內的房屋，最多可以偷竊的金額為dp[i]。如果偷第i房間，那么dp[i] = dp[i - 2] + nums[i]，即：第i-1房一定是不考慮的，找出下標i-2（包括i-2）以內的房屋，最多可以偷竊的金額為dp[i-2] 加上第i房間偷到的錢。如果不偷第i房間，那么dp[i] = dp[i - 1]，即考慮i-1房。

通過代碼：

class Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 0)return 0;if(nums.size() == 1)return nums[0];vector<int> dp(nums.size(), 0);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for(int i = 2; i < nums.size(); i++)dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);return dp[nums.size() - 1];}
};

213.打家劫舍II

力扣題目鏈接

題目：你是一個專業(yè)的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現(xiàn)金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警 。

給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

思路：如果偷竊了第一間房屋，則不能偷竊最后一間房屋，因此偷竊房屋的范圍是第一間房屋到最后第二間房屋；如果偷竊了最后一間房屋，則不能偷竊第一間房屋，因此偷竊房屋的范圍是第二間房屋到最后一間房屋。所以問題就轉化為了兩個上一題，最后取最大值即可。

通過代碼：

class Solution {
public:int myrob(vector<int> &nums, int start, int end){if(end - start == 1)return nums[start];vector<int> dp(nums.size(), 0);dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for(int i = start + 2; i < end; i++)dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);return dp[end - 1];}int rob(vector<int>& nums) {if(nums.size() == 0)return 0;if(nums.size() == 1)return nums[0];int res1 = myrob(nums, 0, nums.size() - 1);int res2 = myrob(nums, 1, nums.size());return max(res1, res2);}
};

337.打家劫舍 III

力扣題目鏈接

題目：小偷又發(fā)現(xiàn)了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為root。除了root之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。如果 兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。

給定二叉樹的root 。返回 在不觸動警報的情況下 ，小偷能夠盜取的最高金額。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/

思路一：記憶化搜索。

通過代碼：

class Solution {
public:unordered_map<TreeNode*, int> map;int rob(TreeNode* root) {if(map.find(root) != map.end())return map[root];if(!root)return 0;if(!root -> left && !root -> right){map[root] = root -> val;return root -> val;}// 偷父節(jié)點int val1 = root -> val;if(root -> left)val1 += rob(root -> left -> left) + rob(root -> left -> right);if(root -> right)val1 += rob(root -> right -> left) + rob(root -> right -> right);// 不偷父節(jié)點int val2 = rob(root -> left) + rob(root -> right);map[root] = max(val1, val2);return map[root];}
};

思路二：樹形dp。遞歸函數的返回值是一個長度為2的數組：dp[0]表示不偷當前節(jié)點所得到的最大值，dp[1]表示偷當前節(jié)點所得到的最大值。在單層遞歸中，如果偷當前節(jié)點，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; 。如果不偷當前節(jié)點，那么左右孩子就可以偷，至于到底偷不偷一定是選一個最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);。最后當前節(jié)點的狀態(tài)就是{val2, val1};

通過代碼：

class Solution {
public:vector<int> robTree(TreeNode *cur){if(!cur)return {0, 0};vector<int> left = robTree(cur -> left);vector<int> right = robTree(cur -> right);// 偷curint val1 = cur -> val + left[0] + right[0];// 不偷curint val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}int rob(TreeNode* root) {vector<int> res = robTree(root);return max(res[0], res[1]);}
};

121. 買賣股票的最佳時機

力扣題目鏈接

題目：給定一個數組prices，它的第i個元素prices[i]表示一支給定股票第i天的價格。

你只能選擇某一天買入這只股票，并選擇在未來的某一個不同的日子賣出該股票。設計一個算法來計算你所能獲取的最大利潤。返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回0 。

思路一：貪心。

通過代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int res = INT_MIN;int low = INT_MAX;for(int i = 0; i < prices.size(); i++){low = min(low, prices[i]);res = max(res, prices[i] - low);}return res;}
};

思路二：動態(tài)規(guī)劃。相鄰兩天的股票價格做差，得到當天持有所能產生的收益beni。問題就轉化為：在beni中找到一段連續(xù)的時間，使得收益最大。dp[i]表示持有到第i天所能產生的最大收益。對于新擴展進來的一天，如果選擇持有，那么累計收益就為dp[i - 1] + beni[i]；如果選擇不持有，那么收益就要從當天重新計算，beni[i]。二者取最大值即可。

通過代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size() < 2)return 0;vector<int> beni;for(int i = 1; i < prices.size(); i++)beni.push_back(prices[i] - prices[ i- 1]);int n = beni.size(), res;vector<int> dp(n, 0);dp[0] = beni[0];res = dp[0];for(int i = 1; i < n; i++){dp[i] = max(dp[i - 1] + beni[i], beni[i]);res = max(res, dp[i]);}return res <= 0 ? 0 : res;}
};

122.買賣股票的最佳時機II

力扣題目鏈接

題目：給你一個整數數組prices，其中prices[i]表示某支股票第i天的價格。在每一天，你可以決定是否購買和/或出售股票。你在任何時候最多只能持有一股股票。你也可以先購買，然后在同一天出售。返回你能獲得的最大利潤 。

思路：在貪心一章我們用收集每天的正利潤來做，這里用動態(tài)規(guī)劃做。dp[i][0]表示第i天不持有股票的最大收益，dp[i][1]表示第i天持有股票的最大收益。對于dp[i][0]，可以由前一天的兩個狀態(tài)推出：如果前一天也沒有持有股票并且今天也選擇不持有股票，那么收益就為dp[i-1][0]，如果前一天持有了股票并且今天選擇不持有，即賣出，收益為dp[i-1][1]+prices[i]，取二者較大值更新狀態(tài)即可。dp[i][1]同理，如果前一天沒有持有股票，今天選擇持有股票，收益為dp[i-1][0]-prices[i]（購買股票需要花錢，所以要減去prices[i]），如果前一天持有了股票，并且今天不賣出，收益為dp[i-1][1]，取二者較大值更新狀態(tài)即可。

通過代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int>(2,0));dp[0][1] = -prices[0];for(int i = 1; i < prices.size(); i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return dp[prices.size() - 1][0];}
};

123.買賣股票的最佳時機III

力扣題目鏈接

題目：給定一個數組，它的第i個元素是一支給定的股票在第i天的價格。設計一個算法來計算你所能獲取的最大利潤。你最多可以完成兩筆交易。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

思路：一天一共就有五個狀態(tài)，

1. 沒有操作 （其實我們也可以不設置這個狀態(tài)）
2. 第一次持有股票
3. 第一次不持有股票
4. 第二次持有股票
5. 第二次不持有股票

dp[i][j]中 i表示第i天，j為 [0 - 4] 五個狀態(tài)，dp[i][j]表示第i天狀態(tài)j所剩最大現(xiàn)金。注意，狀態(tài)j表示第i天仍然處于這個狀態(tài)。

達到dp[i][1]狀態(tài)，有兩個具體操作：

• 操作一：第i天買入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
• 操作二：第i天沒有操作，而是沿用前一天買入的狀態(tài)，即：dp[i][1] = dp[i - 1][1]

二者取較大值就是dp[i][1]更新后的狀態(tài)。剩下的同理。

通過代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(), vector<int> (5, 0));dp[0][1] = -prices[0];dp[0][3] = -prices[0];for(int i = 1; i < prices.size(); i++){dp[i][0] = dp[i - 1][0];dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]);dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3]);dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]);}return dp[prices.size() - 1][4];}
};

188.買賣股票的最佳時機IV

力扣題目鏈接

題目：給你一個整數數組prices和一個整數k ，其中prices[i]是某支給定的股票在第i天的價格。設計一個算法來計算你所能獲取的最大利潤。你最多可以完成k筆交易。也就是說，你最多可以買k次，賣k次。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

思路：類似于上一題，只不過進行了推廣，可以買賣k次。接著上一題的狀態(tài)往下排：第三次持有股票，第三次不持有股票……可以發(fā)現(xiàn)，奇數下標都是持有股票，偶數下標都是不持有股票，而且狀態(tài)更新也只用到上一層相同位置和其左邊一個位置。用一個循環(huán)完成這個重復操作即可。

通過代碼：

class Solution {
public:int maxProfit(int k, vector<int>& prices) {vector<int> dp(2 * k + 1, 0);for(int i = 1; i < 2 * k + 1; i += 2)dp[i] = -prices[0];for(int i = 1; i < prices.size(); i++)for(int j = 1; j < 2 * k + 1; j++){if(j % 2 == 1)dp[j] = max(dp[j], dp[j - 1] - prices[i]);elsedp[j] = max(dp[j], dp[j - 1] + prices[i]);}return dp[2 * k];}
};

309.最佳買賣股票時機含冷凍期

力扣題目鏈接

題目：給定一個整數數組prices，其中第 prices[i]表示第i天的股票價格 。設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

• 賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

思路：首先劃分狀態(tài)。0：持有股票（可能是今天買的，也可能是之前買的）；1：不持有股票，并且是兩天前就賣出的，冷凍期已過；2：今天剛賣出股票；3：昨天賣的股票，今天是冷凍期。

要想得到狀態(tài)0，可能昨天就持有了股票，即dp[i-1][0]，也可能昨天冷凍期已過，今天選擇買入，即dp[i-1][1] - prices[i]，也可能昨天是冷凍期，今天買入，即dp[i-1][3] - prices[i]，三者取最大值更新即可。要想得到狀態(tài)1，可能昨天就是狀態(tài)1，即dp[i-1][1]，也可能昨天是冷凍期，即dp[i-1][3]，二者取最大值即可。要想得到狀態(tài)2，只可能昨天持有股票，即dp[i-1][0]+prices[i]；要想得到狀態(tài)3，只可能昨天剛賣出股票，即dp[i-1][2]。

通過代碼：

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int> (4, 0));dp[0][0] = -prices[0];for(int i = 1; i < n; i++){dp[i][0] = max({dp[i - 1][0], dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]});dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] = dp[i - 1][0] + prices[i];dp[i][3] = dp[i - 1][2];}return max({dp[n - 1][1], dp[n - 1][2], dp[n - 1][3]});}
};

714.買賣股票的最佳時機含手續(xù)費

力扣題目鏈接

題目：給定一個整數數組prices，其中prices[i]表示第i天的股票價格 ；整數fee代表了交易股票的手續(xù)費用。你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了。返回獲得利潤的最大值。

注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費。

思路：類似于買賣股票的最佳時機II，只不過多了一個手續(xù)費，在賣出的時候減去手續(xù)費即可。

通過代碼：

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<int> dp(2, 0);dp[1] = -prices[0];for(int i = 1; i < prices.size(); i++){dp[0] = max(dp[0], dp[1] + prices[i] - fee);dp[1] = max(dp[1], dp[0] - prices[i]);}return dp[0];}
};

300.最長遞增子序列

力扣題目鏈接

題目：給你一個整數數組nums，找到其中最長嚴格遞增子序列的長度。

子序列是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7]是數組[0,3,1,6,2,2,7]的子序列。

思路：dp[i]表示以nums[i]結尾的最長子序列長度。位置i的最長遞增子序列等于j從0到i-1各個位置的最長升序子序列+1的最大值。

通過代碼：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int res = 1;for(int i = 1; i < nums.size(); i++){for(int j = 0; j < i; j++)if(nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1);res = max(res, dp[i]);}return res;}
};

674. 最長連續(xù)遞增序列

力扣題目鏈接

題目：給定一個未經排序的整數數組，找到最長且連續(xù)遞增的子序列，并返回該序列的長度。

連續(xù)遞增的子序列可以由兩個下標l和r（l < r）確定，如果對于每個l <= i < r，都有nums[i] < nums[i + 1]，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]就是連續(xù)遞增子序列。

思路：dp[i]：以下標i為結尾的連續(xù)遞增的子序列長度為dp[i]。如果nums[i] > nums[i - 1]，那么以i為結尾的連續(xù)遞增的子序列長度一定等于以i - 1為結尾的連續(xù)遞增的子序列長度 + 1 。

通過代碼：

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int res = 1;for(int i = 1; i < nums.size(); i++){if(nums[i] > nums[i - 1])dp[i] = dp[i - 1] + 1;res = max(res, dp[i]);}return res;}
};

718. 最長重復子數組

力扣題目鏈接

題目：給兩個整數數組nums1和nums2，返回兩個數組中公共的 、長度最長的子數組的長度 。

思路：dp[i][j]表示以數組1中第i個數結尾（即nums1[i-1]）、數組2中第j個數結尾（即nums2[j-1]）的最長公共子數組的長度。如果nums1[i-1]和nums2[j-1]相同，當前的最長公共子數組的長度就要更新為dp[i-1][j-1]+1。之所以如此定義dp數組，是為了減少初始化的麻煩。如果從下標0開始算，第0行和第0列就要單獨初始化。

通過代碼：

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size(), len2 = nums2.size();if(len1 == 0 || len2 == 0)return 0;vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 0));int res = 0;for(int i = 1; i <= len1; i++)for(int j = 1; j <= len2; j++){if(nums1[i - 1] == nums2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;res = max(res, dp[i][j]);}return res;}
};

1143.最長公共子序列

力扣題目鏈接

題目：給定兩個字符串text1和text2，返回這兩個字符串的最長公共子序列的長度。如果不存在公共子序列 ，返回0 。

一個字符串的子序列是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

• 例如，"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。

兩個字符串的公共子序列是這兩個字符串所共同擁有的子序列。

思路：類似上一題，只不過上一題要求連續(xù)，這一題可以不連續(xù)。dp[i][j]表示長度為[0, i - 1]的字符串text1與長度為[0, j - 1]的字符串text2的最長公共子序列長度。之所以如此設置還是為了避免初始化的麻煩。如果text1[i - 1] 與 text2[j - 1]相同，那么找到了一個公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 與 text2[j - 1]不相同，那就看看text1[0, i - 2]與text2[0, j - 1]的最長公共子序列 和 text1[0, i - 1]與text2[0, j - 2]的最長公共子序列，取最大的。

通過代碼：

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int len1 = text1.size(), len2 = text2.size();vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 0));for(int i = 1; i <= len1; i++)for(int j = 1; j <= len2; j++){if(text1[i - 1] == text2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}return dp[len1][len2];}
};

1035.不相交的線

力扣題目鏈接

題目：在兩條獨立的水平線上按給定的順序寫下nums1和nums2中的整數?，F(xiàn)在，可以繪制一些連接兩個數字nums1[i]和nums2[j]的直線，這些直線需要同時滿足：

• nums1[i] == nums2[j]
• 且繪制的直線不與任何其他連線（非水平線）相交。

請注意，連線即使在端點也不能相交：每個數字只能屬于一條連線。

以這種方法繪制線條，并返回可以繪制的最大連線數。

思路：只有相同的數字才能連線，不就是公共子序列嗎。不允許線相交就是子序列得按順序來。所以本題和上一題最長公共子序列是一樣的，代碼都只要改個數組名。

通過代碼：

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size(), len2 = nums2.size();vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 0));for(int i = 1; i <= len1; i++)for(int j = 1; j <= len2; j++){if(nums1[i - 1] == nums2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}return dp[len1][len2];}
};

53. 最大子序和

力扣題目鏈接

題目：給你一個整數數組nums ，請你找出一個具有最大和的連續(xù)子數組（子數組最少包含一個元素），返回其最大和。子數組是數組中的一個連續(xù)部分。

思路：上次使用貪心做的，這回用動規(guī)。dp[i]表示包括下標i（以nums[i]為結尾）的最大連續(xù)子序列和為dp[i]。對于nums[i]，可以選擇接在前一個序列后面，則和為dp[i-1]+nums[i]，也可以選擇自己單開一個序列，則和為nums[i]，選一個大的更新即可。

通過代碼：

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int> dp(nums.size(), 0);dp[0] = nums[0];int res = dp[0];for(int i = 1; i < nums.size(); i++){dp[i] = max(nums[i], dp[i - 1] + nums[i]);res = max(res, dp[i]);}return res;}
};

392.判斷子序列

力扣題目鏈接

題目：給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。

思路一：很容易想到通過雙指針遍歷兩個串即可。

通過代碼：

class Solution {
public:bool isSubsequence(string s, string t) {int i = 0, j = 0;while(i < s.size() && j < t.size()){if(s[i] == t[j])i++;j++;}return i == s.size();}
};

思路二：動態(tài)規(guī)劃。dp[i][j]表示以下標i-1為結尾的字符串s，和以下標j-1為結尾的字符串t，相同子序列的長度為dp[i][j]。如果s[i-1]和t[j-1]相等，相同子序列長度自然要在dp[i-1][j-1]的基礎上加1。如果不相等，就相當于t[j-1]沒出現(xiàn)過，結果還是和dp[i][j-1]一樣。

通過代碼：

class Solution {
public:bool isSubsequence(string s, string t) {int len1 = s.size(), len2 = t.size();vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 0));for(int i = 1; i <= len1; i++)for(int j = 1; j <= len2; j++){if(s[i - 1] == t[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = dp[i][j - 1];}return dp[len1][len2] == len1;}
};

115.不同的子序列

力扣題目鏈接

題目：給你兩個字符串s和t，統(tǒng)計并返回在s的子序列中t出現(xiàn)的個數，結果需要對$ 10^9+7 $取模。

思路：dp[i][j]表示以j為結尾的s子序列中出現(xiàn)以i為結尾的t的個數為dp[i][j]。當s[i]與t[j]相等時，dp[i][j]可以有兩部分組成。一部分是用s[j]來匹配，那么個數為dp[i - 1][j - 1]。即不需要考慮當前s子串和t子串的最后一位字母，所以只需要dp[i-1][j-1]。另一部分是不用s[j]來匹配，個數為dp[i][j - 1]，兩部分相加即為總個數。當s[j]與t[i]不相等時，dp[i][j]肯定無法用s[j]來匹配，個數即為dp[i][j-1]。初始化比較特殊，需要考慮t[0]在s中的子序列個數。

通過代碼：

class Solution {
public:int numDistinct(string s, string t) {const int mod = 1e9 + 7;int len1 = s.size(), len2 = t.size();vector<vector<int>> dp(len2, vector<int> (len1, 0));if(s[0] == t[0])dp[0][0] = 1;for(int i = 1; i < len1; i++)if(t[0] == s[i])dp[0][i] = dp[0][i - 1] + 1;elsedp[0][i] = dp[0][i - 1];for(int i = 1; i < len2; i++)for(int j = 1; j < len1; j++){if(t[i] == s[j])dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;elsedp[i][j] = dp[i][j - 1];}return dp[len2 - 1][len1 - 1];}
};

583. 兩個字符串的刪除操作

力扣題目鏈接

題目：給定兩個單詞word1和word2，返回使得word1和word2相同所需的最小步數。每步可以刪除任意一個字符串中的一個字符。

思路：刪完之后剩的不就是最長公共子序列嗎。所以這道題和最長公共子序列一樣的，求出最長公共子序列的長度之后，用兩個單詞的長度和減去最長公共子序列的長度就好了。

通過代碼：

class Solution {
public:int minDistance(string word1, string word2) {int len1 = word1.size(), len2 = word2.size();vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 0));for(int i = 1; i <= len1; i++)for(int j = 1; j <= len2; j++){if(word1[i - 1] == word2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}return len1 + len2 - 2 * dp[len1][len2];}
};

72. 編輯距離

力扣題目鏈接

題目：給你兩個單詞word1和word2， 請返回將word1轉換成word2所使用的最少操作數 。你可以對一個單詞進行如下三種操作：

• 插入一個字符
• 刪除一個字符
• 替換一個字符

思路：dp[i][j]表示以下標i-1為結尾的字符串word1，和以下標j-1為結尾的字符串word2，最少編輯次數為dp[i][j]。如果正在比較的兩個字母相等，說明不用任何操作，最少編輯次數還是前一次的次數dp[i-1][j-1]。如果不相等，此時就有三種操作了：插入、刪除和替換。

首先插入和刪除操作需要的次數是一樣的。例如單詞ad和單詞a，可以刪除第一個單詞的d，也可以在第二個單詞末尾添加一個d，所需次數都是1。因此只需要考慮刪除操作即可。刪除可以刪word1[i-1]也可以刪word2[j-1]，對應的次數分別為dp[i-1][j]+1和dp[i][j-1]+1。

對于替換操作，替換完成之后當前比較的兩個字母都是一樣的了。就類似于正在比較的兩個字母相等的情況，次數為dp[i-1][j-1]+1。

上述三者取最小的更新狀態(tài)即可。初始化時，由于一個單詞長度為0，所以另一個單詞只能刪除全部字母，因此初始化為另一個單詞的字母數即可。

通過代碼：

class Solution {
public:int minDistance(string word1, string word2) {int len1 = word1.size(), len2 = word2.size();vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 0));for(int i = 0; i <= len1; i++)dp[i][0] = i;for(int i = 0; i <= len2; i++)dp[0][i] = i;for(int i = 1; i <= len1; i++)for(int j = 1; j <= len2; j++){if(word1[i - 1] == word2[j - 1])dp[i][j] = dp[i - 1][j - 1];elsedp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;}return dp[len1][len2];}
};

647. 回文子串

力扣題目鏈接

題目：給你一個字符串s，請你統(tǒng)計并返回這個字符串中回文子串的數目。回文字符串是正著讀和倒過來讀一樣的字符串。子字符串是字符串中的由連續(xù)字符組成的一個序列。

思路一：動態(tài)規(guī)劃。dp[i][j]表示區(qū)間[i,j]的子串是否是回文子串。

• 如果字符s[i]和s[j]不同，區(qū)間[i,j]肯定不是回文串，dp[i][j]為false；
• 如果字符s[i]和s[j]相同，
  • 如果i和j相同，即整個區(qū)間只有一個字符，那區(qū)間[i,j]還是回文串，dp[i][j]為true；
  • 如果i和j相差1（相鄰），即整個區(qū)間只有兩個字符，那區(qū)間[i,j]還是回文串，dp[i][j]為true；
  • 如果i和j不相鄰，區(qū)間[i+1, j-1]是回文串那整個就是回文串，即dp[i][j]取決于dp[i+1][j-1]。

通過代碼：

class Solution {
public:int countSubstrings(string s) {int res = 0;int n = s.size();vector<vector<bool>> dp(n, vector<bool> (n, false));for(int i = n - 1; i >= 0; i--)for(int j = i; j < n; j++){if(s[i] == s[j]){if(j - i <= 1)	// 情況一和情況二{dp[i][j] = true;res++;}else if(dp[i + 1][j - 1]){dp[i][j] = true;res++;}}}return res;}
};

思路二：雙指針。判斷回文子串可以從中心向兩邊擴散判斷，依次枚舉中心即可，注意中心可能有一個字符也可能是兩個字符。

通過代碼：

class Solution {
public:int extend(string s, int i, int j){int res = 0;while(i >= 0 && j < s.size() && s[i] == s[j]){i--;j++;res++;}return res;}int countSubstrings(string s) {int res = 0;for(int i = 0; i < s.size(); i++){res += extend(s, i, i);		// 以i為中心向兩邊擴散res += extend(s, i, i + 1);	// 以i和i+1為中心向兩邊擴散}return res;}
};

516.最長回文子序列

力扣題目鏈接

題目：給你一個字符串s，找出其中最長的回文子序列，并返回該序列的長度。

子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的一個序列。

思路：dp[i][j]表示區(qū)間[i,j]范圍內最長回文子序列的長度。如果s[i]==s[j]，在s[i+1, j-1]兩邊加上相同的字符s[i]和s[j]就能得到新的回文子序列，因此dp[i][j]=dp[i+1][j-1]+2；如果s[i]!=s[j]，則要考慮單獨加入哪個字母能夠使得長度更大，即dp[i][j]=max(dp[i][j-1], dp[i+1][j])。

注意，i和j相同的時候需要手動初始化長度為1。

通過代碼：

class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int> (n, 0));for(int i = 0; i < n; i++)dp[i][i] = 1;for(int i = n - 1; i >= 0; i--)for(int j = i + 1; j < n; j++){if(s[i] == s[j])dp[i][j] = dp[i + 1][j - 1] + 2;elsedp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);}return dp[0][n - 1];}
};