509. 斐波那契數(shù)

力扣題目鏈接

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

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

給定 n ，請(qǐng)計(jì)算 F(n) 。

思路：數(shù)據(jù)量不大，遞推一下

通過(guò)代碼：

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. 爬樓梯

力扣題目鏈接

假設(shè)你正在爬樓梯。需要n階你才能到達(dá)樓頂。

每次你可以爬1或2個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

思路：每一級(jí)臺(tái)階都可以由前兩個(gè)臺(tái)階走到，前一個(gè)臺(tái)階跨一步，前兩個(gè)臺(tái)階跨兩步

通過(guò)代碼：

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. 使用最小花費(fèi)爬樓梯

力扣題目鏈接

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

你可以選擇從下標(biāo)為0 或下標(biāo)為1的臺(tái)階開(kāi)始爬樓梯。

請(qǐng)你計(jì)算并返回達(dá)到樓梯頂部的最低花費(fèi)。

思路：可以有兩個(gè)途徑得到dp[i]，一個(gè)是dp[i-1]一個(gè)是dp[i-2]。dp[i-1]跳到dp[i]需要花費(fèi)dp[i - 1] + cost[i - 1]。dp[i-2]跳到dp[i]需要花費(fè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])

通過(guò)代碼：

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.不同路徑

力扣題目鏈接

題目：一個(gè)機(jī)器人位于一個(gè)m x n網(wǎng)格的左上角（起始點(diǎn)在下圖中標(biāo)記為“Start”）。機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。問(wèn)總共有多少條不同的路徑？

思路：每個(gè)網(wǎng)格只能從其上方或左邊過(guò)來(lái)，因此其路徑數(shù)為其上方和左側(cè)之和。

通過(guò)代碼：

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

力扣題目鏈接

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

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

通過(guò)代碼：

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. 整數(shù)拆分

力扣題目鏈接

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

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

通過(guò)代碼：

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.不同的二叉搜索樹(shù)

力扣題目鏈接

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

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

通過(guò)代碼：

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. 分割等和子集

力扣題目鏈接

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

思路：首先排除一些明顯無(wú)法分割的情況：元素?cái)?shù)量小于2、總和為奇數(shù)、最大元素超過(guò)總和的一半。將問(wèn)題轉(zhuǎn)化為01背包，取一些數(shù)使得其和為target。定義dp數(shù)組，dp[i][j]表示能否在下標(biāo)為0到i的范圍選一些數(shù)使得和為j。對(duì)于新擴(kuò)展進(jìn)來(lái)的數(shù)nums[i]，我們有兩種選擇，一是不選，那么結(jié)果就為dp[i-1][j]，二是選，結(jié)果就為dp[i-1][j-nums[i]]。只要這兩個(gè)結(jié)果中的一個(gè)為true，那么dp[i][j]就為true。

通過(guò)代碼：

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

力扣題目鏈接

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

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

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

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

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

通過(guò)代碼：

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.目標(biāo)和

力扣題目鏈接

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

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

返回可以通過(guò)上述方法構(gòu)造的、運(yùn)算結(jié)果等于target的不同表達(dá)式的數(shù)目。

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

通過(guò)代碼：

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.一和零

力扣題目鏈接

題目：給你一個(gè)二進(jìn)制字符串?dāng)?shù)組strs和兩個(gè)整數(shù)m和n 。請(qǐng)你找出并返回 strs 的最大子集的長(zhǎng)度，該子集中最多有m個(gè)0和n個(gè)1 。

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

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

通過(guò)代碼：

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

力扣題目鏈接

題目：給你一個(gè)整數(shù)數(shù)組coins表示不同面額的硬幣，另給一個(gè)整數(shù)amount表示總金額。請(qǐng)你計(jì)算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無(wú)法湊出總金額，返回0。

假設(shè)每一種面額的硬幣有無(wú)限個(gè)。 題目數(shù)據(jù)保證結(jié)果符合 32 位帶符號(hào)整數(shù)。

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

通過(guò)代碼：

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. 組合總和 Ⅳ

力扣題目鏈接

題目：給你一個(gè)由 不同 整數(shù)組成的數(shù)組nums，和一個(gè)目標(biāo)整數(shù)target。請(qǐng)你從nums中找出并返回總和為target的元素組合的個(gè)數(shù)。

題目數(shù)據(jù)保證答案符合 32 位整數(shù)范圍。

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

通過(guò)代碼：

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. 零錢兌換

力扣題目鏈接

題目：給你一個(gè)整數(shù)數(shù)組coins，表示不同面額的硬幣；以及一個(gè)整數(shù)amount，表示總金額。計(jì)算并返回可以湊成總金額所需的最少的硬幣個(gè)數(shù) 。如果沒(méi)有任何一種硬幣組合能組成總金額，返回-1 。你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的。

思路：典型的完全背包。湊足總額為j - coins[i]的最少個(gè)數(shù)為dp[j - coins[i]]，那么只需要加上一個(gè)錢幣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，遞推的時(shí)候還要注意無(wú)解的情況。

通過(guò)代碼：

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.完全平方數(shù)

力扣題目鏈接

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

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

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

通過(guò)代碼：

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.單詞拆分

力扣題目鏈接

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

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

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

通過(guò)代碼：

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.打家劫舍

力扣題目鏈接

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

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你不觸動(dòng)警報(bào)裝置的情況下，一夜之內(nèi)能夠偷竊到的最高金額。

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

通過(guò)代碼：

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

力扣題目鏈接

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

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 在不觸動(dòng)警報(bào)裝置的情況下 ，今晚能夠偷竊到的最高金額。

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

通過(guò)代碼：

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)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為root。除了root之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹(shù)”。如果 兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。

給定二叉樹(shù)的root 。返回 在不觸動(dòng)警報(bào)的情況下 ，小偷能夠盜取的最高金額。

/*** 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) {}* };*/

思路一：記憶化搜索。

通過(guò)代碼：

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é)點(diǎn)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é)點(diǎn)int val2 = rob(root -> left) + rob(root -> right);map[root] = max(val1, val2);return map[root];}
};

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

通過(guò)代碼：

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. 買賣股票的最佳時(shí)機(jī)

力扣題目鏈接

題目：給定一個(gè)數(shù)組prices，它的第i個(gè)元素prices[i]表示一支給定股票第i天的價(jià)格。

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

思路一：貪心。

通過(guò)代碼：

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;}
};

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

通過(guò)代碼：

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.買賣股票的最佳時(shí)機(jī)II

力扣題目鏈接

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

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

通過(guò)代碼：

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.買賣股票的最佳時(shí)機(jī)III

力扣題目鏈接

題目：給定一個(gè)數(shù)組，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格。設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成兩筆交易。

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

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

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

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

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

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

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

通過(guò)代碼：

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.買賣股票的最佳時(shí)機(jī)IV

力扣題目鏈接

題目：給你一個(gè)整數(shù)數(shù)組prices和一個(gè)整數(shù)k ，其中prices[i]是某支給定的股票在第i天的價(jià)格。設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成k筆交易。也就是說(shuō)，你最多可以買k次，賣k次。

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

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

通過(guò)代碼：

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.最佳買賣股票時(shí)機(jī)含冷凍期

力扣題目鏈接

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

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

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

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

要想得到狀態(tài)0，可能昨天就持有了股票，即dp[i-1][0]，也可能昨天冷凍期已過(guò)，今天選擇買入，即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]。

通過(guò)代碼：

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.買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)

力扣題目鏈接

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

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

思路：類似于買賣股票的最佳時(shí)機(jī)II，只不過(guò)多了一個(gè)手續(xù)費(fèi)，在賣出的時(shí)候減去手續(xù)費(fèi)即可。

通過(guò)代碼：

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.最長(zhǎng)遞增子序列

力扣題目鏈接

題目：給你一個(gè)整數(shù)數(shù)組nums，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。

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

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

通過(guò)代碼：

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. 最長(zhǎng)連續(xù)遞增序列

力扣題目鏈接

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

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

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

通過(guò)代碼：

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. 最長(zhǎng)重復(fù)子數(shù)組

力扣題目鏈接

題目：給兩個(gè)整數(shù)數(shù)組nums1和nums2，返回兩個(gè)數(shù)組中公共的 、長(zhǎng)度最長(zhǎng)的子數(shù)組的長(zhǎng)度 。

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

通過(guò)代碼：

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.最長(zhǎng)公共子序列

力扣題目鏈接

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

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

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

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

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

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

通過(guò)代碼：

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.不相交的線

力扣題目鏈接

題目：在兩條獨(dú)立的水平線上按給定的順序?qū)懴?code>nums1和nums2中的整數(shù)?，F(xiàn)在，可以繪制一些連接兩個(gè)數(shù)字nums1[i]和nums2[j]的直線，這些直線需要同時(shí)滿足：

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

請(qǐng)注意，連線即使在端點(diǎn)也不能相交：每個(gè)數(shù)字只能屬于一條連線。

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

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

通過(guò)代碼：

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. 最大子序和

力扣題目鏈接

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

思路：上次使用貪心做的，這回用動(dòng)規(guī)。dp[i]表示包括下標(biāo)i（以nums[i]為結(jié)尾）的最大連續(xù)子序列和為dp[i]。對(duì)于nums[i]，可以選擇接在前一個(gè)序列后面，則和為dp[i-1]+nums[i]，也可以選擇自己?jiǎn)伍_(kāi)一個(gè)序列，則和為nums[i]，選一個(gè)大的更新即可。

通過(guò)代碼：

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 的子序列。

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

思路一：很容易想到通過(guò)雙指針遍歷兩個(gè)串即可。

通過(guò)代碼：

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();}
};

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

通過(guò)代碼：

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.不同的子序列

力扣題目鏈接

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

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

通過(guò)代碼：

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. 兩個(gè)字符串的刪除操作

力扣題目鏈接

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

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

通過(guò)代碼：

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. 編輯距離

力扣題目鏈接

題目：給你兩個(gè)單詞word1和word2， 請(qǐng)返回將word1轉(zhuǎn)換成word2所使用的最少操作數(shù) 。你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：

• 插入一個(gè)字符
• 刪除一個(gè)字符
• 替換一個(gè)字符

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

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

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

上述三者取最小的更新?tīng)顟B(tài)即可。初始化時(shí)，由于一個(gè)單詞長(zhǎng)度為0，所以另一個(gè)單詞只能刪除全部字母，因此初始化為另一個(gè)單詞的字母數(shù)即可。

通過(guò)代碼：

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. 回文子串

力扣題目鏈接

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

思路一：動(dòng)態(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相同，即整個(gè)區(qū)間只有一個(gè)字符，那區(qū)間[i,j]還是回文串，dp[i][j]為true；
  • 如果i和j相差1（相鄰），即整個(gè)區(qū)間只有兩個(gè)字符，那區(qū)間[i,j]還是回文串，dp[i][j]為true；
  • 如果i和j不相鄰，區(qū)間[i+1, j-1]是回文串那整個(gè)就是回文串，即dp[i][j]取決于dp[i+1][j-1]。

通過(guò)代碼：

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;}
};

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

通過(guò)代碼：

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為中心向兩邊擴(kuò)散res += extend(s, i, i + 1);	// 以i和i+1為中心向兩邊擴(kuò)散}return res;}
};

516.最長(zhǎng)回文子序列

力扣題目鏈接

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

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

思路：dp[i][j]表示區(qū)間[i,j]范圍內(nèi)最長(zhǎng)回文子序列的長(zhǎng)度。如果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]，則要考慮單獨(dú)加入哪個(gè)字母能夠使得長(zhǎng)度更大，即dp[i][j]=max(dp[i][j-1], dp[i+1][j])。

注意，i和j相同的時(shí)候需要手動(dòng)初始化長(zhǎng)度為1。

通過(guò)代碼：

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];}
};