LeetCode Hot 100：动态规划

LeetCode Hot 100：动态规划

70. 爬楼梯

class Solution {
public:int climbStairs(int n) {if (n == 0)return 0;vector<int> dp(n + 1);// 初始化dp[0] = 1;// 状态转移for (int i = 1; i <= n; i++) {dp[i] += dp[i - 1];if (i >= 2)dp[i] += dp[i - 2];}return dp[n];}
};

118. 杨辉三角

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> ans(numRows);for (int i = 0; i < numRows; i++) {ans[i].resize(i + 1);ans[i][0] = ans[i][i] = 1;}for (int i = 1; i < numRows; i++)for (int j = 1; j < i; j++)ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];return ans;}
};

198. 打家劫舍

class Solution {
public:int rob(vector<int>& nums) {if (nums.empty())return 0;int n = nums.size();if (n == 1)return nums[0];vector<int> dp(n + 1);// 初始化dp[0] = 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. 完全平方数

思路 1：动态规划

class Solution {
public:int numSquares(int n) {// dp[i]: 最少需要多少个数的平方来表示 ivector<int> dp(n + 1);// 初始化dp[0] = 0;for (int i = 1; i <= n; i++) {int minCnt = INT_MAX;for (int j = 1; j * j <= i; j++)minCnt = min(minCnt, dp[i - j * j]);dp[i] = minCnt + 1;}return dp[n];}
};

思路 2：记忆化搜索

@cache
def dfs(i: int, j: int) -> int:if i == 0:return inf if j else 0if j < i * i:return dfs(i - 1, j)  # 只能不选res1 = dfs(i - 1, j)  # 不选res2 = dfs(i, j - i * i) + 1  # 选return min(res1, res2)class Solution:def numSquares(self, n: int) -> int:return dfs(isqrt(n), n)

322. 零钱兑换

class Solution {
public:int coinChange(vector<int>& coins, int amount) {if (coins.empty())return -1;if (amount == 0)return 0;int n = coins.size();if (n == 1 && amount % coins[0])return -1;// dp[i]: vector<int> dp(amount + 1, INT_MAX / 2);// 初始化dp[0] = 0;// 状态转移for (int i = 1; i <= amount; i++)for (int& coin : coins) {if (i < coin)continue;dp[i] = min(dp[i], dp[i - coin] + 1);}return dp[amount] == INT_MAX / 2 ? -1 : dp[amount];}
};

139. 单词拆分

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.length();// dp[i]: s[0,...,i] 是否可以利用 wordDict 拼接出来vector<bool> dp(n + 1, false);// 初始化dp[0] = true;// 状态转移for (int i = 1; i <= n; i++)for (string& word : wordDict) {int len = word.length();if (i >= len && s.substr(i - len, len) == word)dp[i] = dp[i] | dp[i - len];}return dp[n];}
};

300. 最长递增子序列

思路 1：贪心 + 二分查找

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> lis;for (int& num : nums) {auto it = lower_bound(lis.begin(), lis.end(), num);if (it == lis.end())lis.push_back(num); // >=num 的 lis[j] 不存在else*it = num;}return lis.size();}
};

思路 2：动态规划

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.empty())return 0;int n = nums.size();if (n == 1)return 1;vector<int> dp(n, 1);// 初始化for (int i = 0; i < n; i++)dp[i] = 1;int maxLen = 0;// 状态转移for (int i = 0; i < n; i++)for (int j = 0; j < i; j++) {if (nums[j] < nums[i])dp[i] = max(dp[i], dp[j] + 1);maxLen = max(maxLen, dp[i]);}return maxLen;}
};

152. 乘积最大子数组

class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<int> minF(n, 0), maxF(n, 0);// 初始化minF[0] = nums[0];maxF[0] = nums[0];// 状态转移for (int i = 1; i < n; i++) {minF[i] =min({nums[i], minF[i - 1] * nums[i], maxF[i - 1] * nums[i]});maxF[i] =max({nums[i], minF[i - 1] * nums[i], maxF[i - 1] * nums[i]});}return *max_element(maxF.begin(), maxF.end());}
};

416. 分割等和子集

思路 1：0-1背包

class Solution {
public:bool canPartition(vector<int>& nums) {if (nums.empty())return false;int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 == 1)return false;int n = nums.size();int target = sum / 2;// dp[i,j]：前i个数字、总和不超过j的情况下，能否满足j == targetvector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));// 初始化dp[0][0] = true;// 状态转移for (int i = 1; i <= n; i++)for (int j = 1; j <= target; j++) {int w = nums[i - 1];if (j >= w)dp[i][j] = dp[i - 1][j] || dp[i - 1][j - w]; // 选elsedp[i][j] = dp[i - 1][j]; // 不选}return dp[n][target];}
};

思路 1：栈

class Solution {
public:int longestValidParentheses(string s) {if (s.empty())return 0;int maxLen = 0;stack<int> stk;stk.push(-1);for (int i = 0; i < s.length(); i++) {if (s[i] == '(')stk.push(i);else {stk.pop();if (stk.empty())stk.push(i);elsemaxLen = max(maxLen, i - stk.top());}}return maxLen;}
};

思路 2：动态规划

class Solution {
public:int longestValidParentheses(string s) {if (s.empty())return 0;int n = s.length();// dp[i]: 表示以下标 i 字符结尾的最长有效括号的长度vector<int> dp(n, 0);int maxLen = 0;// 状态转移for (int i = 1; i < n; i++) {if (s[i] == ')') {if (s[i - 1] == '(')dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')dp[i] = dp[i - 1] + ((i - dp[i - 1] - 2) >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;}maxLen = max(maxLen, dp[i]);}return maxLen;}
};