题目链接：编辑距离给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符方法一：二维数组+动态规划class Solution { public: int minDistance(string word1, string word2) { vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0)); for (int i = 0; i < dp.size(); i++) { dp[i][0] = i; } for (int j = 0; j < dp[0].size(); j++) { dp[0][j] = j; } for (int i = 1; i < dp.size(); i++) { for (int j = 1; j < dp[i].size(); j++) { // dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; // if (word1[i - 1] == word2[j - 1]) { // dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]); // } dp[i][j] = word1[i-1] == word2[j-1] ? dp[i-1][j-1] : min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; } } return dp.back().back(); } };
题目链接：最长公共子序列给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。方法一：二维数组+动态规划class Solution { public: int f[1010][1010]; int longestCommonSubsequence(string text1, string text2) { int n = text1.size(); int m = text2.size(); for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { f[i+1][j+1] = text1[i] == text2[j] ? f[i][j] + 1 : max(f[i][j+1],f[i+1][j]); } } return f[n][m]; } };
题目链接：单词拆分给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。方法一：动态规划class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { vector<bool> dp(s.size()+1); dp[0] = true; for (int i = 1;i <= s.size();i++) { for (auto& word:wordDict) { int sz = word.size(); if (i - sz >= 0 && s.substr(i-sz,sz) == word) dp[i] = dp[i] || dp[i-sz]; } } return dp[s.size()]; } };
题目链接：分割等和子集给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。方法一：动态规划+二维数组class Solution { public: bool canPartition(vector<int>& nums) { vector dp(nums.size() + 1, vector<int> (2e4 + 10, 0)); double sum = 0; for (auto x : nums) { sum += x; } double target = sum / 2; for (int i = 0;i < nums.size();i++) { for (int j = 0;j <= target;j++) { if (j < nums[i]) { dp[i+1][j] = dp[i][j]; }else dp[i + 1][j] = max(dp[i][j], dp[i][j - nums[i]] + nums[i]); } } return dp[nums.size()][target] == target; } };方法二：动态规划+一维数组//一维优化 class Solution { public: bool canPartition(vector<int>& nums) { vector<int> dp(2e4 + 10, 0); double sum = 0; for(int i = 0;i < nums.size(); ++i) sum += nums[i]; double target = double(sum / 2); for(int i = 0; i < nums.size(); ++i) for(int j = target;j >= nums[i]; --j) dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); return dp[target] == target; } };
题目链接：完全平方数给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。方法一：动态规划class Solution { public: int numSquares(int n) { int f[10010]; //f[0] = 0; for (int i = 1;i <= n;i++) { f[i] = i; for (int j = 1;j * j <= i;j++) { f[i] = min(f[i],f[i-j*j]+1); } // f[i] = minn + 1; } return f[n]; } };
题目链接：最长递增子序列给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。方法一：动态规划class Solution { public: int lengthOfLIS(vector<int>& nums) { int f[2550]; f[0] = 1; int ans = 1; for (int i = 1;i < nums.size();i++) { f[i] = 1; for (int j = 0;j < i;j++) { if (nums[j] < nums[i]) { f[i] = max(f[i],f[j] + 1); ans = max(ans,f[i]); } } } return ans; } };方法二：贪心+二分int first_ge(const vector<int>& a, int x) { int l = 0, r = (int)a.size(); // [l, r) while (l < r) { int m = l + (r - l) / 2; if (a[m] >= x) r = m; else l = m + 1; } return l; // 第一个 >= x 的位置（可能等于 a.size()） } int lengthOfLIS(vector<int>& nums) { vector<int> tails; for (int x : nums) { int i = first_ge(tails, x); if (i == (int)tails.size()) tails.push_back(x); else tails[i] = x; } return (int)tails.size(); }
题目链接：乘积最大子数组给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。请注意，一个只包含一个元素的数组的乘积是这个元素的值。方法一：动态规划class Solution { public: int maxProduct(vector<int>& nums) { int u_nums[20010]; int d_nums[20010]; u_nums[0] = nums[0] > 0 ? nums[0] : 1; d_nums[0] = nums[0] < 0 ? nums[0] : 0; int ans = nums[0]; for (int i = 1;i < nums.size();i++) { if (nums[i] >= 0) { ans = max(ans,u_nums[i-1] * nums[i]); u_nums[i] = max(u_nums[i-1] * nums[i],1); d_nums[i] = d_nums[i-1] * nums[i]; }else { ans = max(ans,d_nums[i-1] * nums[i]); u_nums[i] = max(d_nums[i-1] * nums[i],1); d_nums[i] = u_nums[i-1] * nums[i]; } } return ans; } };
题目链接：零钱兑换给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。方法一：动态规划 + 二维数组class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); vector f(n + 1, vector<int>(amount + 1, INT_MAX / 2)); f[0][0] = 0; for (int i = 0;i < n;i++) { for (int j = 0;j <= amount;j++) { if (j < coins[i]) { f[i+1][j] = f[i][j]; }else { f[i+1][j] = min(f[i][j],f[i+1][j-coins[i]] + 1); } } } int ans = f[n][amount]; return ans < INT_MAX / 2 ? ans : -1; } };方法二：动态规划+一维数组class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> f(amount + 1, INT_MAX / 2); f[0] = 0; for (int x : coins) { for (int i = x;i <= amount;i++) { f[i] = min(f[i],f[i-x] + 1); } } int ans = f[amount]; return ans < INT_MAX / 2 ? ans : -1; } };
题目链接：打家劫舍你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。方法一：动态规划class Solution { public: int rob(vector<int>& nums) { int f[110]; f[0] = nums[0]; if (nums.size() == 1) return f[0]; f[1] = max(nums[0],nums[1]); for (int i = 2;i < nums.size();i++) { f[i] = max(f[i-1],nums[i] + f[i-2]); } return f[nums.size()-1]; } };
题目链接：杨辉三角给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。方法一：动态规划class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> ans; ans.push_back({1}); for (int i = 1;i < numRows;i++) { vector<int> tmp; for (int j = 0;j <= i;j++) { if (j == 0 || j == i) tmp.push_back(1); else { tmp.push_back(ans[i-1][j-1] + ans[i-1][j]); } } ans.push_back(tmp); } return ans; } };