Solution 1: #Recursion
class Solution {
public:
int fib(int n) {
if(n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
};Solution 2: #DP
class Solution {
public:
int fib(int n) {
if(n <= 1) return n;
vector<int>dp(n + 1, 0);
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};Solution 1: #DP
class Solution {
public:
int climbStairs(int n) {
if(n <= 2) return n;
vector<int> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
};Solution 2: #Two Pointers
class Solution {
public:
int climbStairs(int n) {
if(n == 0 || n == 1) return 1;
int prev = 1;
int curr = 1;
int tmp = 0;
for(int i = 2; i <= n; i++){
tmp = curr;
curr = prev + curr;
prev = tmp;
}
return curr;
}
};Solution 1: #DP
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = dp[1] = 0;
for(int i = 2; i <= n; i++){
dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp[n];
}
};Solution 2: #DP
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
for(int i = 2; i < cost.size(); i++) cost[i] += min(cost[i - 1], cost[i - 2]);
return min(cost[cost.size() - 1], cost[cost.size() - 2]);
}
};Solution 3: #Two Pointers
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int a = cost[0], b = cost[1];
for(int i = 2; i < cost.size(); i++){
int c = min(a, b) + cost[i];
a = b;
b = c;
}
return min(a, b);
}
};Solution 1: #DP
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int i = 0; i < m; i++) dp[i][0] = 1;
for(int j = 0; j < n; j++) dp[0][j] = 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];
}
};Solution 2: #Memoization
class Solution {
public:
int help(int i, int j, int m, int n, vector<vector<int>>& dp){
if(i == m - 1 && j == n - 1) return 1;
if(i >= m || j >= n) return 0;
if(dp[i][j] != -1) return dp[i][j]; // memoization
int down = help(i + 1, j, m, n, dp);
int right = help(i, j + 1, m, n, dp);
return dp[i][j] = down + right; // （i, j)到(m-1, n - 1)的所有路径数
}
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, - 1));
return help(0, 0, m, n, dp);
}
};Solution 1: #DP
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for(int i = 0; i < m; i++){
if(obstacleGrid[i][0] == 1) break;
dp[i][0] = 1;
}
for(int j = 0; j < n; j++){
if(obstacleGrid[0][j] == 1) break;
dp[0][j] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};Solution 2: #Memoization
class Solution {
public:
int m, n;
int numberOfPaths(int i, int j, vector<vector<int>>& obs, int dp[][101]){
if(i == m - 1 && j == n - 1) return 1;
if(i == m || j == n || obs[i][j] == 1) return 0;
if(dp[i][j] != -1) return dp[i][j];
int down = numberOfPaths(i + 1, j, obs, dp);
int right = numberOfPaths(i, j + 1, obs, dp);
return dp[i][j] = down + right;
}
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
m = obstacleGrid.size();
n = obstacleGrid[0].size();
if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;
int dp[101][101];
memset(dp, -1, sizeof(dp));
return numberOfPaths(0, 0, obstacleGrid, dp);
}
};Solution 1: #DP
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1, 0);
dp[2] = 1;
for(int i = 3; i <= n; i++){
for(int j = 1; j <= i / 2; j++){
dp[i] = max(dp[i], max((i - j) * j, j * dp[i - j]));
}
}
return dp[n];
}
};96. Unique Binary Search Trees
Solution 1: #DP
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};416. Partition Equal Subset Sum
Solution 1: #DP
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(auto x : nums) sum += x;
if(sum % 2 != 0) return false;
sum /= 2;
vector<bool> dp(sum + 1, false);
dp[0] = true;
for(auto num : nums){
for(int i = sum; i >= num; i--){
dp[i] = dp[i] || dp[i - num];
}
}
return dp[sum];
}
};Solution 1: #DP
#include<bits/stdc++.h>
using namespace std;
int main(){
int m, n;
cin >> m >> n;
vector<vector<int>> sample;
vector<int> costs(m);
vector<int> values(m);
for(int i = 0; i < m; i++){
cin >> costs[i];
}
for(int i = 0; i < m; i++){
cin >> values[i];
}
vector<int> dp(n + 1, 0);
for(int i = 0; i < m; i++){
for(int j = n; j >= costs[i]; j--){
dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
}
}
cout << dp[n] << endl;
}Solution 1: #DP
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001, 0);
int sum = 0;
for(auto x : stones) sum += x;
int target = sum / 2; // 看作抽象的背包
for(int i = 0; i < stones.size(); i++){
for(int j = target; j >= stones[i]; j--){
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};Solution 1: #DP
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 zero = 0;
int one = 0;
for(char c : s){
if(c == '0') zero++;
if(c == '1') one++;
}
for(int i = m; i >= zero; i--){
for(int j = n; j >= one; j--){
dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1);
}
}
}
return dp[m][n];
}
};Solution 1: #DP
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, v;
cin >> n >> v;
vector<int> weight(n, 0);
vector<int> cost(n, 0);
for(int i = 0; i < n; i++){
cin >> weight[i] >> cost[i];
}
vector<int> dp(v + 1, 0);
for(int i = 0; i < n; i++){
for(int j = weight[i]; j <= v; j++){
if(j - weight[i] >= 0){
dp[j] = max(dp[j], dp[j - weight[i]] + cost[i]);
}
}
}
cout << dp[v] << endl;
return 0;
}Solution 1: #DP
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];
}
};Solution 1: #DP
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for(int i = 0; i <= target; i++){
for(int j = 0; j < nums.size(); j++){
if(i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) dp[i] += dp[i - nums[j]];
}
}
return dp[target];
}
};Solution 2: #Recursion, #DP
class Solution {
public:
int find(vector<int>& dp, vector<int>& nums, int target){
if(target < 0) return 0;
if(dp[target] != -1) return dp[target];
if(target == 0) return 1;
int ans = 0;
for(int i = 0; i < nums.size(); i++){
ans += find(dp, nums, target - nums[i]);
}
return dp[target] = ans;
}
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, -1);
return find(dp, nums, target);
}
};Solution 1: #DP
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i - j >= 0) dp[i] += dp[i - j];
}
}
cout << dp[n] << endl;
}Solution 1：#DP
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for(int i = 0; i < coins.size(); i++){
for(int j = coins[i]; j <= amount; j++){
if(dp[j - coins[i]] != INT_MAX){
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
}
}
}
if(dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};Solution 1: #DP
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for(int i = 1; i * i <= n; i++){
for(int j = i * i; j <= n; j++){
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
};Solution 1: #DP
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()];
}
};Solution 1: #DP
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> dp(nums.size() + 1, 0);
dp[1] = nums[0];
for(int i = 2; i <= nums.size(); i++){
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[nums.size()];
}
};Solution 1: #DP
class Solution {
public:
int help(int start, int end, vector<int>& nums){
if(end == start) 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 - 2] + nums[i], dp[i - 1]);
}
return dp[end];
}
int rob(vector<int>& nums) {
if(nums.size() == 1) return nums[0];
int result1 = help(0, nums.size() - 2, nums);
int result2 = help(1, nums.size() - 1, nums);
return max(result1, result2);
}
};Solution 1: #DP
class Solution {
public:
vector<int> robTree(TreeNode* cur){
if(cur == NULL) return {0, 0}; // 0不偷，1偷
vector<int> left = robTree(cur->left);
vector<int> right = robTree(cur->right);
int val1 = cur->val + left[0] + right[0];
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};
}
int rob(TreeNode* root) {
vector<int> result = robTree(root);
return max(result[0], result[1]);
}
};121. Best Time to Buy and Sell Stock
Solution 1: #Greedy
class Solution {
public:
int maxProfit(vector<int>& prices) {
int low = INT_MAX;
int result = 0;
for(int i = 0 ; i < prices.size(); i++){
low = min(low, prices[i]);
result = max(result, prices[i] - low);
}
return result;
}
};Solution 2: #DP
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(2, 0));
// 0持有，1不持有
dp[0][0] = -prices[0];
for(int i = 1; i < n; i++){
dp[i][0] = max(-prices[i], dp[i - 1][0]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[n - 1][1];
}
};122. Best Time to Buy and Sell Stock II
Solution 1: #DP
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = -prices[0]; // have the stock on the day 0;
dp[0][1] = 0; // don't have the stock on the day 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[n - 1][1]; // don't have the stock on the day n - 1
}
};123. Best Time to Buy and Sell Stock III
Solution 1: #DP
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() == 0) return 0;
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][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[prices.size() - 1][4];
}
};188. Best Time to Buy and Sell Stock IV
Solution 1: #DP
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
for(int j = 1; j < 2 * k; j += 2){
dp[0][j] = -prices[0];
}
for(int i = 1; i < prices.size(); i++){
for(int j = 0; j < 2 * k - 1; j += 2){
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k];
}
};309. Best Time to Buy and Sell Stock with Cooldown
Solution 1: #DP
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 0) return 0;
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], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - 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][3], max(dp[n - 1][1], dp[n - 1][2]));
}
};714. Best Time to Buy and Sell Stock with Transaction Fee
Solution 1: #DP
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 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] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
}
return dp[n - 1][1];
}
};300. Longest Increasing Subsequence
Solution 1: #DP
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n <= 1) return n;
vector<int> dp(n, 1);
int result = 0;
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
}
if(dp[i] > result) result = dp[i];
}
return result;
}
};674. Longest Continuous Increasing Subsequence
Solution 1: #DP
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
if(n <= 1) return n;
vector<int> dp(n + 1, 1);
int result = 0;
for(int i = 1; i < n; i++){
if(nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
result = max(result, dp[i]);
}
return result;
}
};718. Maximum Length of Repeated Subarray
Solution 1: #DP
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
int result = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i -1][j - 1] + 1;
if(dp[i][j] > result) result = dp[i][j];
}
}
return result;
}
};1143. Longest Common Subsequence
Solution 2: #DP
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
return dp[n][m];
}
};Solution 1: #DP
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
}
};Solution 1: #DP
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 1, 0);
dp[0] = nums[0];
int result = dp[0];
for(int i = 1; i < n; i++){
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
result = max(result, dp[i]);
}
return result;
}
};Solution 1: #DP
class Solution {
public:
bool isSubsequence(string s, string t) {
int n = s.size();
int m = t.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];
}
}
return dp[n][m] == n;
}
};Solution 1: #DP
这里有个testcase巨奇怪要爆超时，uint64_t是一个数据类型，表示64位无符号整数。
class Solution {
public:
int numDistinct(string s, string t) {
long n = s.size();
long m = t.size();
vector<vector<uint64_t>> dp(n + 1, vector<uint64_t>(m + 1, 0));
for(auto i = 0; i < n; i++) dp[i][0] = 1;
for(auto j = 1; j < m; j++) dp[0][j] = 0;
for(auto i = 1; i <= n; i++){
for(auto j = 1; j <= m; j++){
if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
else dp[i][j] = dp[i - 1][j];
}
}
return dp[n][m];
}
};583. Delete Operation for Two Strings
Solution 1: #DP
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size();
int m = word2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++) dp[i][0] = i;
for(int j = 1; j <= m; j++) dp[0][j] = j;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
}
return dp[n][m];
}
};Solution 1: #DP
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for(int i = 1; i <= m; i++) dp[i][0] = i;
for(int j = 1; j <= n; j++) dp[0][j] = j;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
return dp[m][n];
}
};Solution 1: #Brute Force(TLE❗️最后一个test case真的很让人无语)
class Solution {
public:
bool ispalindrome(string s, int start, int length){
string t = s.substr(start, length);
string r = t;
reverse(r.begin(), r.end());
return t == r;
}
int countSubstrings(string s) {
int n = s.size();
int count = 0;
for(int i = 1; i <= n; i++){
for(int start = 0; start <= n - i; start++){
if(ispalindrome(s, start, i)) count++;
}
}
return count;
}
};Solution 2: #DP
class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
vector<vector<bool>> dp(n + 1, vector<bool>(n + 1, false));
int result = 0;
for(int i = n; i >= 0; i--){
for(int j = i; j < n; j++){
if(s[i] == s[j]){ // single char
if(j - i <= 1){
dp[i][j] = true;
result++;
}
else{
if(dp[i + 1][j - 1] == true){
dp[i][j] = true;
result++;
}
}
}
}
}
return result;
}
};516. Longest Palindromic Subsequence
Solution 1: #DP
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;
else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
};