LeetCode 每周算法 9（动态规划）

动态规划算法：

class Solution {  
public:  // 定义函数，输入n表示楼梯的总级数，输出爬到楼梯顶部的不同方式的数量  int climbStairs(int n) {  // 如果楼梯只有一级，那么只有一种方式爬到顶部，即直接走那一级  if (n == 1) return n;  // 使用一个长度为3的数组dp来存储动态规划的状态  // 我们只需要存储最近的三个状态，因为每次计算新状态时只依赖于前两个状态  vector<int> dp(3);  // 初始化dp数组，dp[1]表示一级楼梯有一种方式，dp[2]表示两级楼梯有两种方式（一次一级或一次两级）  dp[1] = 1;  dp[2] = 2;  // 从第三级楼梯开始计算，直到第n级楼梯  for (int i = 3; i <= n; i++) {  // 计算当前楼梯可以有多少种方式到达，即到达前一级的方式加上到达前两级的方式  int sum = dp[1] + dp[2];  // 更新dp数组，为下一次循环做准备  // dp[1]存储前一级楼梯的方式数量，即原来的dp[2]  dp[1] = dp[2];  // dp[2]存储当前楼梯的方式数量，即刚刚计算出的sum  dp[2] = sum;  }  // 返回dp[2]，即到达第n级楼梯的不同方式的数量  return dp[2];  }  
};

class Solution {  
public:  // 定义一个函数，接收一个整数numRows作为参数，返回一个二维向量，表示生成的杨辉三角形  vector<vector<int>> generate(int numRows) {  // 创建一个二维向量result，用于存储生成的杨辉三角形，大小为numRows行  vector<vector<int>> result(numRows);  // 遍历每一行  for (int i = 0; i < numRows; i++) {  // 将当前行的向量大小调整为i+1，因为杨辉三角形的每一行元素个数等于行号+1  result[i].resize(i + 1);  // 每行的第一个和最后一个元素都是1  result[i][0] = result[i][i] = 1;  // 遍历当前行的中间元素（从第二个元素到倒数第二个元素）  for (int j = 1; j < i; j++) {  // 当前元素的值等于上一行对应位置的元素与上一行前一个位置的元素之和  // 这是杨辉三角形生成规则的核心  result[i][j] = result[i - 1][j] + result[i - 1][j - 1];  }  }  // 返回生成的杨辉三角形  return result;  }  
};

class Solution {  
public:  // 定义一个函数，接受一个整数向量作为参数，返回能够偷窃到的最大金额  int rob(vector<int>& nums) {  if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];// 创建一个动态规划数组dp，其大小与输入数组nums相同  // dp[i]表示偷窃到第i个房屋时能得到的最大金额  int dp[nums.size()];  // 初始化dp数组的前两个元素  // 对于第一个房屋，只能偷这一个，所以dp[0] = nums[0]  dp[0] = nums[0];  // 对于第二个房屋，我们有两种选择：偷第一个不偷第二个，或者偷第二个不偷第一个  // 取这两种情况中的较大值作为dp[1]的值  dp[1] = max(nums[0], nums[1]); // 从第三个房屋开始遍历到最后一个房屋  for (int i = 2; i < nums.size(); i++) {  // 对于每个房屋i，我们有两个选择：  // 1. 偷当前房屋i，那么就不能偷i-1的房屋，因此金额是nums[i] + dp[i - 2]  // 2. 不偷当前房屋i，那么金额就是dp[i - 1]（即偷到i-1房屋时的最大金额）  // 取这两种情况中的较大值作为dp[i]的值  dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);  }  // 返回偷窃到最后一个房屋时能得到的最大金额  return dp[nums.size() - 1];  }  
};

class Solution {  
public:  // 定义函数numSquares，接收一个整数n，返回将n表示为若干个完全平方数之和所需的最少个数  int numSquares(int n) {  // 创建一个动态规划数组dp，大小为n+1，初始化为INT_MAX（表示一个非常大的数，这里用作表示当前值还未被计算）  // dp[i]表示将整数i表示为若干个完全平方数之和所需的最少个数  vector<int> dp(n + 1, INT_MAX);  // 金额0不需要任何完全平方数，所以dp[0]设为0  dp[0] = 0;  // 遍历从1到n的所有整数  for (int i = 1; i <= n; i++) {  // 遍历所有可能的完全平方数j*j（其中j从1开始，直到j*j不超过当前整数i）  for (int j = 1; j * j <= i; j++) {  // 更新dp[i]，表示将整数i表示为若干个完全平方数之和所需的最少个数  // 取当前dp[i]和dp[i - j * j] + 1中的较小值  dp[i] = min(dp[i - j * j] + 1, dp[i]);  }  }  // 返回将整数n表示为若干个完全平方数之和所需的最少个数   return dp[n];  }  
};

class Solution {  
public:  // 定义函数coinChange，接收一个整数数组coins（表示可用的硬币面值）和一个整数amount（表示要找零的金额）  int coinChange(vector<int>& coins, int amount) {  // 创建一个动态规划数组dp，大小为amount+1，初始化为INT_MAX（表示一个非常大的数，这里用作表示无法构成该金额）  // dp[i]表示金额i所需的最少硬币数  vector<int> dp(amount + 1, INT_MAX);  // 金额0不需要任何硬币，所以dp[0]设为0  dp[0] = 0;  // 遍历从1到amount的所有金额  for (int i = 1; i <= amount; i++) {  // 遍历所有硬币面值  for (int j = 0; j < coins.size(); j++) {  // 如果当前金额i减去硬币面值coins[j]的结果非负// 并且dp[i - coins[j]]不是INT_MAX（即可以构成金额i - coins[j]）  if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX) {  // 更新dp[i]，表示金额i所需的最少硬币数  // dp[i - coins[j]] + 1表示使用当前硬币面值coins[j]后，剩余金额i - coins[j]所需的最少硬币数加1  // 取当前dp[i]和dp[i - coins[j]] + 1中的较小值  dp[i] = min(dp[i - coins[j]] + 1, dp[i]);  }  }  }  // 如果dp[amount]仍然是INT_MAX，表示无法用给定的硬币面值组合成amount金额  // 返回-1表示无法找零  if (dp[amount] == INT_MAX) return -1;  // 返回金额amount所需的最少硬币数  return dp[amount];  }  
};

class Solution {  
public:  // 函数接受一个字符串 s 和一个字符串向量 wordDict 作为参数  // 返回一个布尔值，表示字符串 s 是否可以被 wordDict 中的单词拆分  bool wordBreak(string s, vector<string>& wordDict) {  // 将字典中的单词存储到一个无序集合中，以便快速查找  unordered_set<string> wordSet(wordDict.begin(), wordDict.end());  // 使用动态规划方法，dp[i] 表示字符串 s 的前 i 个字符能否被成功拆分  // 初始化 dp 数组，大小为 s.size() + 1，初始值全为 false  // dp[0] 表示空字符串，可以被认为是可以成功拆分的，因此 dp[0] = true  vector<bool> dp(s.size() + 1, false);  dp[0] = true;  // 遍历字符串 s 的每一个位置 i（从 1 到 s.size()）  for (int i = 1; i <= s.size(); i++) {    // 对于每一个位置 i，再遍历它之前的每一个位置 j（从 0 到 i-1）  // 目的是尝试用 s[j..i-1] 这个子串作为一个单词进行拆分  for (int j = 0; j < i; j++) {        // 提取 s 中从 j 到 i-1 的子串  string word = s.substr(j, i - j);  // 检查这个子串是否在字典中，并且 s 的前 j 个字符能否被成功拆分  // 如果这两个条件都满足，则 s 的前 i 个字符也可以被成功拆分  if (wordSet.find(word) != wordSet.end() && dp[j]) {  dp[i] = true;  // 注意：这里不需要继续遍历 j 了，因为 dp[i] 被设置为 true 后，  // 后续的 j 值不会改变 dp[i] 的结果（因为 dp[i] 已经是 true 了）  // 但为了保持代码的直观性，我们仍然保留完整的内层循环  }  }  }  // 返回 dp[s.size()]，即整个字符串 s 是否可以被成功拆分  return dp[s.size()];  }  
};

class Solution {  
public:  // 方法：计算最长递增子序列的长度  // 参数：nums - 整数数组  // 返回值：最长递增子序列的长度  int lengthOfLIS(vector<int>& nums) {  // 如果数组的大小小于或等于1，则最长递增子序列的长度就是数组的大小  if (nums.size() <= 1) return nums.size();  // 创建一个动态规划数组dp，dp[i]表示以nums[i]结尾的最长递增子序列的长度  // 初始化时，每个元素的最长递增子序列至少包含它自己，所以dp[i]都初始化为1  vector<int> dp(nums.size(), 1);  // 变量result用于记录当前找到的最长递增子序列的长度  int result = 0;  // 遍历数组nums，从第二个元素开始（因为单个元素自己就是一个递增子序列）  for (int i = 1; i < nums.size(); i++) {  // 对于每个nums[i]，遍历它之前的所有元素nums[j]（j < i）  for (int j = 0; j < i; j++) {  // 如果nums[i]大于nums[j]，说明nums[i]可以加入到以nums[j]结尾的递增子序列中  // 此时，以nums[i]结尾的最长递增子序列长度至少为dp[j] + 1  // 更新dp[i]为dp[i]和dp[j] + 1中的较大值  if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);  }  // 更新result为当前找到的最长递增子序列的长度（即dp数组中的最大值）  result = max(result, dp[i]);  }  // 返回最长递增子序列的长度  return result;  }  
};

class Solution {  
public:  int maxProduct(vector<int>& nums) {  // 获取数组的大小  int n = nums.size();  // 初始化结果变量为数组的第一个元素  int result = nums[0];  // 创建两个动态规划数组，分别用于存储到当前位置为止的最大乘积和最小乘积  vector<int> dpMax(n + 1, 0), dpMin(n + 1, 0);  dpMax[0] = nums[0]; // 初始化最大乘积数组的第一个元素  dpMin[0] = nums[0]; // 初始化最小乘积数组的第一个元素// 遍历nums数组中的每个元素  for (int i = 1; i < n; i++) {  // 更新dpMax[i]：它可以是当前元素nums[i]本身，  // 或者是前一个位置的最大乘积dpMax[i-1]乘以当前元素nums[i]得到的乘积，  // 或者是前一个位置的最小乘积dpMin[i-1]乘以当前元素nums[i]（考虑负数乘以负数得到正数的情况）中的最大值  dpMax[i] = max(nums[i], max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));  // 更新dpMin[i]：逻辑与dpMax[i]类似，但这里是求最小值  dpMin[i] = min(nums[i], min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));  // 更新结果变量为当前找到的最大乘积  result = max(result, dpMax[i]);  }  // 返回最大乘积  return result;  }  
};

class Solution {  
public:  // 方法：判断数组nums是否可以分割成两个和相等的子集  bool canPartition(vector<int>& nums) {  int n = nums.size(); // 获取数组的长度  if (n < 2) {  // 如果数组长度小于2，无法分割成两个子集，返回false  return false;  }  int sum = accumulate(nums.begin(), nums.end(), 0); // 计算数组所有元素的总和  int maxNum = *max_element(nums.begin(), nums.end()); // 找到数组中的最大值  // 如果总和是奇数，无法分割成两个和相等的子集，返回false  if (sum & 1) {  return false;  }  // 计算目标和，即将总和除以2  int target = sum / 2;  // 如果数组中的最大值已经超过了目标和，无法分割，返回false  if (maxNum > target) {  return false;  }  // 创建一个二维动态规划数组dp，dp[i][j]表示前j个元素是否能组成和为i的子集，int比bool更快vector<vector<int>> dp(target + 1, vector<int>(n, 0));  // 初始化dp数组的第一列，表示和为0的子集总是可以组成的  for (int j = 0; j < n; j++) {  dp[0][j] = true;  }  // 动态规划过程  for (int i = 1; i < target + 1; i++) { // 遍历背包for (int j = 1; j < n; j++) { // 遍历物品// 如果当前和i大于等于当前数字nums[j]，则有两种选择：包含nums[j]或不包含nums[j]  if (i >= nums[j]) {  dp[i][j] = dp[i][j - 1] | dp[i - nums[j]][j - 1];  } else {  // 如果当前和i小于当前数字nums[j]，则只能选择不包含nums[j]  dp[i][j] = dp[i][j - 1];  }  }  }  // 返回结果，即前n个元素是否能组成和为target的子集（也即是否能分割成两个和相等的子集）  return dp[target][n - 1];  }  
};

class Solution {  
public:  // 函数接收一个字符串s，返回最长有效括号的长度  int longestValidParentheses(string s) {  // 初始化最长有效括号长度为0  int result = 0, n = s.length();  // 创建一个动态规划数组dp，用于存储以每个位置结尾的最长有效括号长度  // 初始时，所有位置的最长有效括号长度都为0  vector<int> dp(n, 0);  // 从字符串的第二个字符开始遍历（因为需要考虑括号对）  for (int i = 1; i < n; i++) {  // 如果当前字符是右括号')'  if (s[i] == ')') {  // 如果前一个字符是左括号'('，则形成了一对有效括号  if (s[i - 1] == '(') {  // 此时，以i结尾的最长有效括号长度至少为2（这对括号）  // 如果i >= 2，则还需要加上i-2位置的最长有效括号长度（考虑前面的有效括号序列）  dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;  }   // 如果前一个字符不是左括号'('，则检查是否能与前面的某个有效括号序列匹配  else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {  // 如果i-dp[i-1]-1位置是左括号，则形成了一对新的有效括号  // 此时，以i结尾的最长有效括号长度为：前一个位置的最长有效括号长度 + 2  // 如果i-dp[i-1] >= 2，则还需要加上i-dp[i-1]-2位置的最长有效括号长度  dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;  }  // 更新最长有效括号长度  result = max(result, dp[i]);  }  }  // 返回最长有效括号的长度  return result;  }  
};