【LeetCode 热题 100】动态规划 系列_leetcode题库
📁 70. 爬楼梯
状态标识：爬到第i层楼梯时，有多少种方法。
状态转移方程：dp[i] = dp[i-1] + dp[i-2]，表示从走一步和走两步的方式。
初始化：dp[1] = 1 , dp[2] = 2。
返回值：dp[n]，即走到第n层可以有多少种爬法。
class Solution {public: int climbStairs(int n) { int dp[50] = { 0 , 1 , 2}; for(int i = 3 ; i <= n ; ++i) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }};📁 118. 杨辉三角
就是一道找规律的题目，每一列第一个和每一行最后一个初始化为1，其余的为左上方和右上方数之和。
状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。
vector<vector> generate(int numRows) { vector<vector> dp(numRows); for(int i = 0 ; i < numRows ; ++i) dp[i].resize(i + 1) , dp[i][i] = 1 , dp[i][0] = 1; for(int i = 2 ; i < numRows ; ++i) for(int j = 1 ; j < i ; ++j) dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; return dp; }📁 198. 打家劫舍
状态表示：dp[i]表示偷窃到第 i 加时，此时偷取到的最大金额。
转移方程：dp[i] = max(dp[i-1] , dp[i-2] + num[i-1])
初始化：dp[0] = nums[1]，第一家是可以直接偷取到的。
返回值：返回dp[n]，即偷取到最后一家是此时的最大金额。
class Solution {public: int rob(vector& nums) { int n = nums.size(); vector dp(n + 1 , 0); dp[1] = nums[0]; for(int i = 2 ; i <= n ; ++i) dp[i] = max(dp[i-1] , dp[i-2] + nums[i-1]); return dp[n]; }};📁 279. 完全平方数
状态标识：dp[i]表示和为 i 的完全平方数的最小数量。
转移方程：dp[i] = min(dp[i] , dp[i - j * j] + 1)。j * j 表示小于i的完全平方数
初始化：dp[i] = i，将当前数字更新为最大结果，即最坏结果，表示 i 可以由 i 个 1 组成。
返回值：返回dp[n]。
动态规划本身就是一个递推的过程，我们从前往后枚举，当枚举到第i个数的时候，意味着i-1都被枚举完了。因此，当一个数减去一个完全平方数时剩余和一定能在dp数组中找到，并且剩余和已经知道最小完全平方数的最小数量，因此，我们结果只需要在此基础上+1即可。
class Solution {public: int numSquares(int n) { vector dp(n + 1 , 0); for(int i = 1 ; i <= n ; ++i) { dp[i] = i; for(int j = 2 ; j * j <= i ; ++j) { dp[i] = min(dp[i] , dp[i-j*j] + 1); } } return dp[n]; }};📁 322. 零钱兑换
这道题可以看做是上一题的一种变形。
状态标识：dp[i]表示金额为 i 的时，需要的最少硬币数量。
转移方程：dp[i] = min(dp[i] , dp[i - coin] + 1)。
初始化：dp[0] = 0，其余将当前数字更新0x3f3f3f3f，表示目前不能通过硬币各个金额组成选择不能组成（方便返回值的处理）
返回值：返回dp[amoun]。需要注意的是，如果dp[amoun] = 0x3f3f3f3f，需要返回-1。
class Solution {public: int coinChange(vector& coins, int amount) { vector dp(amount + 1, 0x3f3f3f3f); dp[0] = 0; for(int i = 1 ; i <= amount ; ++i) { for(auto coin : coins) if(coin <= i) dp[i] = min(dp[i] , dp[i-coin] + 1); } return dp[amount]==0x3f3f3f3f ? -1 : dp[amount]; }};📁 139. 单词拆分
状态表示：以某个字符为结尾的字符串，能否由wordDict中的word拼接形成。为了快速查找字典里面的单词，我们是用哈希系列容器存储单词。
转移方程：dp[i] = str(j , i)是字典里面的单词 && dp[j - 1]。
初始化：dp[0] = true，表示只有一个字符，并且成功在哈希表中找到。
返回值：dp[n]，以n为结尾的字符串，能否由wordDict中的word拼接形成。
class Solution {public: bool wordBreak(string s, vector& wordDict) { int n = s.size(); vector dp(n + 1 , false); dp[0] = true; unordered_set hash; for(auto word : wordDict) hash.insert(word); for(int i = 1 ; i 0 ; --j) { string tmp = s.substr(j - 1, i - j + 1); if(hash.find(tmp) != hash.end()) dp[i] = dp[j - 1]; if(dp[i] == true) break; } } return dp[n]; }};📁 300. 最长递增子序列
如果想要有一个子序列尽可能的多，那么就要使得子序列中元素相较于前一个元素上升趋势尽可能小，与后一个元素上升趋势尽可能大。通过一个数组dp来维护递增子序列。
1. 当新来一个元素时，如果大于尾部元素，直接插入；
2. 如果小于尾部元素，那么之前就一定存在比他的的一个或者多个元素，因此我们将这个新的较小值更新到子序列中第一个比它的的元素中，使得子序列上升趋势变得更小。
使用二分查找算法，查找子序列中第一个比新来较小值大的的元素，然后更新。
class Solution {public: int lengthOfLIS(vector& nums) { int n = nums.size(); vector ret; ret.push_back(nums[0]); for(int i = 1 ; i ret.back()) ret.push_back(nums[i]); else { int left = 0 , right = ret.size() - 1; while(left > 1; if(ret[mid] < nums[i]) left = mid + 1; else right = mid; } ret[left] = nums[i]; } } return ret.size(); }};📁 152. 乘积最大子数组
遍历数组，每次遍历时，记录乘积最大值，更新结果。问题是乘积最大值怎么更新？
当一个新元素x到来时，与之前连续子数组乘积最大值maxS进行比较 max( x , maxS)。
1. 如果 x 是正数，且maxS也是正数，那么会得到一个更大的正数。
2. 如果 x 是正数，maxS是负数，那么会得到一个更小的数值。
3. 如果 x 是负数，maxS是正数，那么会得到一个更小的数值。
4. 如果 x 是负数，maxS是负数，那么会得到一个更大的数值。
但如果我们记录一个较小值minS，那么 x 如果负数，minS也是负数，就会得到一个更大的值。
即，如果x是正数，必须有一个最大值相乘才能得到更大值；如果x是负数，必须和一个最小值相乘才能得到一个更大值。
核心：负数 x 大=小；负数 x 小=大；正数 x 大=大；正数 x 小=小
class Solution {public: int maxProduct(vector& nums) { int ans = nums[0] , maxI = nums[0] , minI = nums[0]; int n = nums.size(); for(int i = 1 ; i < n ; ++i) { int tmp = maxI; /* nums[i] * tmp: 如果nums[i]是正数, 得到更大值 nums[i] * minI: 如果nums[i]是负数, 得到更大值 */ maxI = max(max(nums[i] , nums[i] * tmp) , nums[i] * minI); /* nums[i] * minI: 如果nums[i]是正数, 得到更小值 nums[i] * tmp: 如果nums[i]是负数, 得到更小值 */ minI = min(min(nums[i] , nums[i] * minI) , nums[i] * tmp); ans = max(ans , maxI); } return ans; }};📁 416. 分割等和子集
就是一道简单的01背包问题。首先判断个数组总和是否为偶数，如果是奇数直接返回false，因为不可能将数组分割成元素和相等的两个子集；如果sum是偶数，令target = sum / 2。需要判断从数组中能否选出一些数，使得这些数之和=target。
状态标识：dp[i][j]: 前i个元素中能否恰好选出 总和为 j 的子集
转移方程：dp[i][j] = (不选第i件，dp[i-1][j]) or (选第i件 dp[i-1][j-nums[i]])
返回值：dp[n][target]。
此外，采用滚动数组进行优化，使得只能一维数组就可以完成上述操作，只不是从前往后遍历改成往后往前遍历。
class Solution {public: bool canPartition(vector& nums) { int sum = 0; for(auto e : nums) sum += e; if(sum % 2 != 0) return false; int n = nums.size(); int target = sum / 2; vector dp(target + 1 , false); dp[0] = true; for(int i = 1 ; i = nums[i-1] ; --j) dp[j] = dp[j] || dp[j- nums[i-1]]; } return dp[target]; }};📁 32. 最长有效括号
状态表示: dp[i]表示 以s[i]为结尾并且包含s[i]的最长有效括号。
状态转移方程:
1. s[i] ==\'(\' 无法组成有效括号 dp[i] = 0;
2. s[i] ==\')\' 取决于之前的有效括号
情况1: s[i-1] == \'(\'
dp[i] = dp[i-2] + 2;
情况2: s[i-1] == \')\'
这里如果想要包含s[i]组成有效括号的字符串，
必须满足 ((...)) 这种形式 , 其中...是未知个数的有效括号子串。
|
v
即 s[i - dp[i-1] - 1] == \'(\'
所以, dp[i] = dp[i-1] + dp[i - dp[i-1] - 2 ] + 2;
初始化:
dp[0] = 0 一个字符不能构成有效括号
class Solution {public: int longestValidParentheses(string s) { int n = s.size(); int ans = 0; vector dp(n + 1 , 0); for(int i = 1 ; i = 0 ? dp[i-2] : 0) + 2; else if(i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == \'(\') dp[i] = dp[i - 1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0); } ans = max(ans , dp[i]); } return ans; }};
