动态规划leetcode专栏
dp入门问题
leetcode 509 斐波那契数
class Solution {
public:
int fib(int n) {
if(n <= 1) {
return n;
}
return fib(n-1) + fib(n-2);
}
};
class Solution {
public:
vector<int> memory = vector<int>(40, -1);
int fib(int n) {
if(n <= 1) {
return n;
}
if (memory[n] != -1) return memory[n];
int a = fib(n-1);
memory[n-1] = a;
int b = fib(n-2);
memory[n-2] = b;
return a + b;
}
};
class Solution {
public:
//1、确定dp数组，以及下标的含义
//2、确定dp数组的递推公式
//3、dp数组如何进行初始化
//4、dp数组的遍历顺序
//5、举例推导dp数组
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];
}
};
class Solution {
public:
int fib(int n) {
if(n <= 1) {
return n;
}
int state1 = 0;
int state2 = 1;
for(int i = 2; i <= n; i++) {
int nextState = state1 + state2;
state1 = state2;
state2 = nextState;
}
return state2;
}
};
leetcode 70 爬楼梯
//1、确定dp数组以及下标的含义
//2、确定递推公式
//3、dp数组如何初始化
//4、确定遍历顺序
//5、举例推导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];
}
};
class Solution {
public:
int climbStairs(int n) {
if(n <= 2) return n;
int state1 = 1;
int state2 = 2;
for(int i = 3; i <= n; i++) {
int nextState = state2 + state1;
state1 = state2;
state2 = nextState;
}
return state2;
}
};
leetcode 746 使用最小花费爬楼梯
//dp[i]的定义：第i个台阶所花费的最少体力为dp[i]。
//递推公式：dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
//dp数组的初始化
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int sumCost = 0;
int N = cost.size();
vector<int> dp(N);
dp[0] = cost[0];
dp[1] = cost[1];
for(int i = 2; i < N; i++) {
dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
}
return min(dp[N-1], dp[N-2]);
}
};
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n+1, 0);
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
return dp[n];
}
};
leetcode 62 不同路径
//机器人从(0,0)位置出发，到(m-1,n-1)终点。
//dp数组以及下标的定义：表示从(0,0)出发，到(i,j)有dp[i][j]条不同的路径。
//状态转移公式：dp[i][j] = dp[i-1][j] + dp[i][j-1];
//dp数组初始化：dp[0][j]=1 dp[i][0]=1
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];
}
};
//超时的代码，递归实现
class Solution {
public:
int uniquePaths(int m, int n) {
return dfs(1, 1, m, n);
}
int dfs(int i, int j, int m, int n) {
if(i > m || j > n) return 0;
if(i == m && j == n) return 1;
return dfs(i+1, j, m, n) + dfs(i, j+1, m, n);
}
};
//回溯
//超时的代码，将机器人行走路径抽象为树模型，采用深度优先搜索的方式搜索到达符合要求的叶子节点数目
class Solution {
public:
int uniquePaths(int m, int n) {
int res = 0;
BackTracking(1, m, 1, n, res);
return res;
}
void BackTracking(int i, int m, int j, int n, int& res) {
if (i == m && j == n) {
res++;
}
if (i > m || j > n) {
return;
}
BackTracking(i+1, m, j, n, res);
BackTracking(i, m, j+1, n, res);
}
};
leetcode 63 不同路径 II
机器人从(0,0)位置出发，到(m-1,n-1)终点。
dp数组以及下标的定义：表示从(0,0)出发，到(i,j)有dp[i][j]条不同的路径。
状态转移公式：dp[i][j] = dp[i-1][j] + dp[i][j-1];
dp数组初始化：dp[0][j]=1 dp[i][0]=1
对于障碍的处理，就是标记对应的dp数组保持初始值0就可以了,需要注意初始化时对障碍物的处理
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 && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
leetcode 64 最小路径和
class Solution {
public int minPathSum(int[][] grid) {
// 定义dfs(i,j) 表示从左上角到第i行第j列这个格子（记作(i,j)）的最小价值和。
return dfs(grid.length - 1, grid[0].length - 1, grid);
}
private int dfs(int i, int j, int[][] grid) {
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
if (i == 0 && j == 0) {
return grid[i][j];
}
return Math.min(dfs(i, j - 1, grid), dfs(i - 1, j, grid)) + grid[i][j];
}
}
class Solution {
public int minPathSum(int[][] grid) {
// 定义dfs(i,j) 表示从左上角到第i行第j列这个格子（记作(i,j)）的最小价值和。
int m = grid.length;
int n = grid[0].length;
int[][] memo = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(memo[i], -1); // -1表示没有计算过
}
return dfs(m - 1, n - 1, grid, memo);
}
private int dfs(int i, int j, int[][] grid, int[][] memo) {
if (i < 0 || j < 0) {
return Integer.MAX_VALUE;
}
if (i == 0 && j == 0) {
return grid[i][j];
}
if (memo[i][j] != -1) {
return memo[i][j];
}
memo[i][j] = Math.min(dfs(i, j - 1, grid, memo), dfs(i - 1, j, grid, memo)) + grid[i][j];
return memo[i][j];
}
}
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 从左上角(0,0)的位置到当前(m,n)位置的路径和是最小的，等于dp[m][n]
int[][] dp = new int[m][n];
// dp数组初始化
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}
leetcode 343 整数拆分
dp定义:dp[i]表示给定整数i拆分后乘积的最大值。(至少拆分成两个整数的乘积和)
状态转移: 让j从1开始遍历，dp[i]可通过j * dp[i - j]得到，同时注意dp[i]对应的值是经过拆分了的，所以还应判断两个数拆分的情况，即j*(i-j)的值，取最大即可。
在遍历过程还要比较当前这两者的较大值更大，还是上一步遍历得到的dp[i]更大，因此得到递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)).为什么递推公式不是 dp[i]=max(i*(i-j)，i*dp[i-j])，是因为，dp[i]在最里层循环被计算了很多次
初始化：严格来说，初始化dp[0]和dp[1]无意义，从2开始拆分才有意义，因此初始化dp[2] = 1，为了计算推导还是初始化dp[1] = 1
确定遍历顺序
举例推导dp数组
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1);
dp[1] = 1;
for(int i = 2; i <= n; i++) {
for(int j = 1; j < i; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
return dp[n];
}
};
leetcode 96 不同的二叉搜索树
//dp[i]定义:1到i为节点组成的二叉搜索树的个数为dp[i]。
//递推关系:dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
//dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]这三部分分别是以1、2、3为头结点
//dp[i] += dp[j-1]*dp[i-j]
//首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出
//节点数为i的状态是依靠 i之前节点数的状态。那么遍历i里面每一个数作为头结点的状态，用j来遍历。
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n + 1);
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];
}
};
//超时代码
//二叉搜索树的中序遍历的结果一定是从1到n
//int dfs(int start, int end) 返回从start到end之间的结点可以构成的子树的数目
class Solution {
public:
int numTrees(int n) {
return dfs(1, n);
}
int dfs(int start, int end) {
if (start >= end) {
return 1;
}
int res = 0;
for (int i = start ; i <= end; i++) { //以i为根节点
res += dfs(start, i - 1) * dfs(i + 1, end);
}
return res;
}
};
0-1背包问题
0-1背包——暴力搜索、回溯法和剪枝限界
0-1背包——动态规划，二维和一维dp数组
纯01背包问题：给我们一个容器，问我们装满该容器的最大价值是多少？
暴力解法求背包中的最佳组合，返回最大价值
i是物品编号，j是背包可以承受的最大重量
//return the bag max value
int dfsVer2(int i, int j, vector<int>& weight, vector<int>& value) {
if (i == 0 || j == 0) {
return 0;
}
if (weight[i] > j) {
return dfsVer2(i - 1, j, weight, value);
}
int value1 = dfsVer2(i - 1, j, weight, value);
int value2 = dfsVer2(i - 1, j - weight[i], weight, value) + value[i];
return max(value1, value2);
}
//using dfs search total result about the value of the bag
void dfsVer1(vector<int>& result, int totval, int i, int j, vector<int>& weight, vector<int>& value) {
if (i < 0 || j < 0) {
return;
}
if (i == 0 || j == 0) {
result.push_back(totval);
return;
}
if (weight[i] > j) {
dfsVer1(result, totval, i - 1, j, weight, value);
}
dfsVer1(result, totval, i - 1, j, weight, value);
dfsVer1(result, totval+value[i], i - 1, j - weight[i], weight, value);
}
leetcode 416 分割等和子集
采用回溯法，但是会超时
//本题要求集合里能否出现总和为 sum / 2 的子集
class Solution {
public:
bool canPartition(vector<int>& nums) {
int res = 0;
for (int i = 0; i < nums.size(); i++) {
res += nums[i];
}
if (res % 2 == 1) return false;
int target = res / 2;
return BackTracking(0, target, nums);
}
bool BackTracking(int i, int target, vector<int>& nums) {
if (i >= nums.size() || target < 0) {
return false;
}
if (target == 0) {
return true;
}
if(BackTracking(i + 1, target - nums[i], nums)) {
return true;
}
else {
if (BackTracking(i + 1, target, nums)) {
return true;
}
}
return false;
}
};
class Solution {
public:
bool canPartition(vector<int>& nums) {
int res = 0;
for (int i = 0; i < nums.size(); i++) {
res += nums[i];
}
if (res % 2 == 1) return false;
int target = res / 2;
bool flag = false;
BackTracking(0, target, nums, flag);
return flag;
}
void BackTracking(int i, int target, vector<int>& nums, bool& flag) {
if (i >= nums.size()) {
return;
}
if (target == 0) {
flag = true;
return;
}
else if (target < 0) {
return;
}
BackTracking(i + 1, target - nums[i], nums, flag);
BackTracking(i + 1, target, nums, flag);
}
};
采用动态规划二维dp数组
//01背包问题，可以把问题抽象为给定一个数组和一个容量为target的背包，能否找到一种组合使背包装满。
//数组的下标相当于物品编号，数组值相等于物品value
//dp[i][j]: 在nums[0, i]集合中选取元素其和等于j，若能找到dp[i][j] = true;(找到物品填满容量j的背包)
//dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
if ((sum & 1) == 1)
return false;
int target = sum / 2;
vector<vector<bool>> dp(nums.size(), vector<bool>(target+1, false));
for(int j = 0; j <= target; j++) {
dp[0][j] = (nums[0] == j ? true : false);
}
for(int i = 1; i < nums.size(); i++) {
for(int j = 0; j <= target; j++) {
if(j >= nums[i]) {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[nums.size()-1][target];
}
};
采用滚动数组将二维降到一维
//dp[i][j]: 在nums[0, i]集合中选取元素其和等于j，若能找到dp[i][j] = true;(找到物品填满容量j的背包)
//dp[j]表示当前能否填满容量为j的背包,若能填满dp[j] == true,否则为false
//状态转移方程为 dp[j] = dp[j] || dp[j-nums[i]]
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
if ((sum & 1) == 1)
return false;
int target = sum / 2;
vector<bool> dp(target+1, false);
for(int i = 0; i < nums.size(); i++) {
for(int j = target; j >= nums[i]; j--) {
if(i == 0) {
dp[j] = (nums[0] == j ? true : false);
}
dp[j] = dp[j] || dp[j-nums[i]];
}
}
return dp[target];
}
};
对于dp数组的定义不同，状态转移方程也不同，按照01背包的定义
dp[j]定义为装满 j 容量的背包所获得的最大价值，将数组中的元素值看成value，则如果dp[target] == target，则返回true。
递推公式：dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
if ((sum & 1) == 1)
return false;
int target = sum / 2;
vector<int> dp(target+1, 0);
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;
}
};
leetcode 1046 最后一块石头的重量
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
multiset<int, greater<int>> st(stones.begin(), stones.end());
while (st.size() > 1) {
int ele1 = *(st.begin());
st.erase(st.begin());
int ele2 = *(st.begin());
st.erase(st.begin());
int tmp = ele1 - ele2;
st.insert(tmp);
}
return *(st.begin());
}
};
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> pq(stones.begin(), stones.end());
while (pq.size() > 1) {
int ele1 = pq.top();
pq.pop();
int ele2 = pq.top();
pq.pop();
int tmp = ele1 - ele2;
if (tmp != 0) pq.push(tmp);
}
return pq.empty() ? 0 : pq.top();
}
};
leetcode 1049 最后一块石头的重量 II
01背包问题，将石头分成两堆，求两堆石头的最小差值，两堆石头的总和为sum，则其中肯定有一堆石头的重量<=sum/2。这一堆石头的重量为dp[j]，dp[j] <= sum/2，本质上我们需要求dp[j]的最大值，即最接近甚至等于sum/2的值，这样才能保证两堆石头的差值最小，两堆石头的差值等于2*(sum/2 - dp[sum/2])。
二维dp:
dp[i][j] 定义为从下标为[0-i]的石头中任意取，装满背包承重量j所产生的最大价值，这里石头的重量==石头的价值，所以dp[i][j] <= j。dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]] + stones[i])
一维dp:
dp[j] 定义为装满背包容量 j 所产生的最大价值，这里的价值就是石头的重量，value = weight。
dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
class Solution {
public:
//dp[i][j]从编号0到i的石头中选择，装满背包j的容量，所能够产生的最大价值
//weight和value数组相同
//dp[i][j] = max(dp[i-1][j], dp[i][j - stones[i]] + stones[j] )
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
int N = stones.size();
for (int i = 0; i < N; i++) {
sum += stones[i];
}
int target = sum / 2;
vector<vector<int>> dp(N, vector<int>(target + 1, 0));
for (int j = target; j >= stones[0]; j--) {
dp[0][j] = stones[0];
}
for (int i = 1; i < N; i++) { //注意这里是从1开始
for (int j = 0; j <= target; j++) {
if (j < stones[i]) {
dp[i][j] = dp[i-1][j];
}
else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j - stones[i]] + stones[i]);
}
}
}
int res = (sum - dp[N-1][target]) - dp[N-1][target];
return res;
}
};
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = accumulate(stones.begin(), stones.end(), 0);
vector<int> dp(sum/2+1, 0);
for(int i = 0; i < stones.size(); i++) { //注意这里一定是从0开始不然就错了
for(int j = sum/2; j >= stones[i]; j--) {
dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
}
}
return sum - 2 * dp[sum/2];
}
};
leetcode 494 目标和
回溯法暴力搜索
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int result = 0;
backtracking(0, result, 0, target, nums);
return result;
}
void backtracking(int k, int& result, int curSum, int target, vector<int>& nums) {
if(k >= nums.size()) {
if(curSum == target) {
result++;
}
return;
}
backtracking(k+1, result, curSum + nums[k], target, nums);
backtracking(k+1, result, curSum - nums[k], target, nums);
}
};
问题简化：给我们一个固定容量的背包，用物品装满这个背包有多少种方法，每个物品最多只选1次？
在一个集合当中我们需要分出两个子集：
加法集合和减法集合
left + right = sum; 加法集合加减法集合
left - right = target;
right = sum - left;
left - (sum - left) = target;
left = (target + sum) / 2 加法集合中全部元素的和
求最终得到的不同表达式的数目就可以转换成求nums中的元素组合成left的所有情况。
dp[i][j]：使用下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。
dp[i][j] = dp[i-1][j]（不需要nums[i]物品就可以填满容量j的包的方法） + dp[i-1][j-nums[i]]（需要nums[i]才可以填满容量j的包的方法）。第i个物品可以选择用它来填j空间，也可以不选择它填j空间，两种决策的方法进行相加。
dp数组初始化，dp[0][0]为1,装满容量为0的背包，有一种方法，就是装0件物品。dp[0][j]，看第一个元素的大小情况，进行赋值。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if ((sum+target) % 2 == 1) return 0;
if (abs(target) > sum) return 0;
int left = (sum + target) / 2;
vector<vector<int>> dp(nums.size(), vector<int>(left + 1, 0));
dp[0][0] = 1;
for(int j = 0; j <= left; j++) {
if(nums[0] == j) {
dp[0][j] = dp[0][j] + 1;
}
}
for(int i = 1; i < nums.size(); i++) {
for(int j = 0; j <= left; j++) {
if(j >= nums[i]) {
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
}
else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[nums.size()-1][left];
}
};
dp[j] 定义为凑满容量为j大小的背包，有dp[j]种方法
根据二维转一维度，状态转移公式，dp[j] = dp[j] + dp[j-nums[i]]
初始化dp[0]=1，装满容量0的背包，装0个物品就行，一种方法
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if ((sum+target) % 2 == 1) return 0;
if (abs(target) > sum) return 0;
int left = (sum+target) / 2;
vector<int> dp(left+1, 0);
dp[0] = 1;
for(int i = 0; i < nums.size(); i++) {
for(int j = left; j >= nums[i]; j--) {
dp[j] = dp[j] + dp[j-nums[i]];
}
}
return dp[left];
}
};
二维费用的01背包问题
P05: 二维费用的背包问题
问题：
二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（背包容量），问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]，两种代价可付出的最大值（两种背包的容量）分别为V和U。物品的价值为w[i]。
算法：
费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：f[i][v][u] = max(f[i-1][v][u], f[i-1][v-a[i]][u-b[i]]+w[i])。如前述方法，可以只使用二维的数组：当每件物品可以取一次时变量v和u采用顺序的循环，当物品有如完全背包问题时采用逆序的循环，当物品有如多重背包问题时拆分物品。
物品总个数的限制
有时，“二维费用”的条件是以一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v，最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0……V][0……M]范围内寻找答案。另外，如果要求“恰取M件物品”，则在f[0……V][M]范围内寻找答案。
小结
事实上，当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。
leetcode 474 一和零
问题简化：装满背包最多需要多少件物品，每件物品含有两个代价值cost1和cost2，背包对应两个代价值也有两个上限M和N。
该问题可以看成二维费用的背包问题，在01背包的基础上增加了一个费用维度，而这道题中的每个字符串相当于一个物品，而该物品的价值可以看成是单位1。对比于求满足费用维度的条件下，物品的最大价值组合，实际上得到的就是最大的子集。
本题strs数组中的元素就是物品，每个物品都是一个，而m和n相当于是一个背包，两个维度的背包。
1、确定dp数组以及下标的含义：dp[i][j]，最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
2、确定递推公式：dp[i][j]可以由前一个strs里的字符串推导出来，设前一个字符串有zeroNum个0，oneNum个1。
dp[i][j]就可以是dp[i-zeroNum][j-oneNum]+1。然后在遍历过程中取dp[i][j]的最大值。
dp[i-zeroNum][j-oneNum]的含义就是，最多有i-zeroNum个0和j-oneNum个1的最大子集的大小。
dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum]+1)这个方程实际上是三维度降低维到了二维，如果把物品的维度加上，则dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-zeroNum][j-oneNum]+1)，所以这里对两个费用维度进行遍历的时候需要采用逆序的方式进行遍历。
在动态规划中，如果第i个状态只与第i-1个状态有关，而不与其他的例如第i - k(0 < k < i)个状态有关，那么意味着此时在空间上有优化的空间，我们可以采用滚动数组或者从后往前的方式填表来代替开辟更高维度的数组。
滚动数组可以理解，但另一种方式是从后往前的方式填表，这是为什么呢？
我们可以举个例子，假设一个状态方程为 dp[i][j] = dp[i-1][j-1] + 1。如果采用从后向前填表，那么我们的dp[i-1][j-1]应该是上一轮计算的结果，因为这一轮我们还没有更新过这个值。但如果采用从前往后填表，那么我们的dp[i-1][j-1]应该是这一轮计算的结果，因为这一轮我们已经更新过这个值。但是我们这个二维dp数组是最初的三维dp数组的一个优化，因此，在状态迁移时，我们需要的是上一轮计算的dp[i-1][j-1]。这就是为什么我们要从后往前填表了，主要是保留上一轮计算的结果不被覆盖。
最原始的版本代码
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<vector<int>>> dp;
for (int i = 0; i <= strs.size(); i++) {
dp.push_back(vector<vector<int>>(m+1, vector<int>(n+1, 0)));
}
for (int k = 1; k <= strs.size(); k++) {
int zeroNum = 0;
int oneNum = 0;
string s = strs[k-1];
for (int x = 0; x < s.size(); x++) {
if (s[x] == '0') {
zeroNum++;
}
else {
oneNum++;
}
}
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i < zeroNum || j < oneNum) {
dp[k][i][j] = dp[k-1][i][j];
}
else {
dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-zeroNum][j-oneNum] + 1);
}
}
}
}
return dp[strs.size()][m][n];
}
};
采用滚动数组降维后的版本
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i = 0; i < strs.size(); i++) {
int oneNum = 0, zeroNum = 0;
for(char c : strs[i]) {
if(c == '0') zeroNum++;
else oneNum++;
}
for(int i = m; i >= zeroNum; i--) {
for(int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum]+1);
}
}
}
return dp[m][n];
}
};
完全背包问题
/*
完全背包和01背包的区别：
完全背包中，同一件物品可以使用无数次，01背包中一件物品只能使用一次。
01背包
for (int i = 0; i < size; i++) { 先遍历物品，再遍历背包，背包需要倒序遍历
for (int j = bagWeight; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
}
}
完全背包
for (int i = 0; i < size; i++) { 先遍历物品，再遍历背包，背包需要倒序遍历
for (int j = weight[i]; j <= bagWeight; j++) {
dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
}
}
对于完全背包，先遍历物品还是先遍历背包得到的结果都是相同的
*/
leetcode 518. 零钱兑换 II
//dp[i][j]：使用下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。
//dp[i][j] = dp[i-1][j]（不需要nums[i]物品就可以填满容量j的包的方法） + dp[i-1][j-nums[i]]（需要nums[i]才可以填满容量j的包的方法）。
//第i个物品可以选择用它来填j空间，也可以不选择它填j空间，两种决策的方法进行相加。
//dp数组初始化，dp[0][0]为1,装满容量为0的背包，有一种方法，就是装0件物品。dp[0][j]，看第一个元素的大小情况，进行赋值。
//dp[j] 定义为凑满容量为j大小的背包，有dp[j]种方法
//根据二维转一维度，状态转移公式，dp[j] = dp[j] + dp[j-nums[i]]
//初始化dp[0]=1，装满容量0的背包，装0个物品就行，一种方法
//dp[i][j]：使用下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。
//dp[i][j] = dp[i-1][j]（不需要nums[i]物品就可以填满容量j的包的方法） + dp[i-1][j-nums[i]]（需要nums[i]才可以填满容量j的包的方法）。
//第i个物品可以选择用它来填j空间，也可以不选择它填j空间，两种决策的方法进行相加。
//dp数组初始化，dp[0][0]为1,装满容量为0的背包，有一种方法，就是装0件物品。dp[0][j]，看第一个元素的大小情况，进行赋值。
//dp[j] 定义为凑满容量为j大小的背包，有dp[j]种方法
//根据二维转一维度，状态转移公式，dp[j] = dp[j] + dp[j-nums[i]]
//初始化dp[0]=1，装满容量0的背包，装0个物品就行，一种方法
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] = dp[j] + dp[j - coins[i]];
}
}
return dp[amount];
}
};
leetcode 377. 组合总和 Ⅳ
//(1, 1, 2)和(1, 2, 1)是两个不同的排列，对于组合来说，两者是相同的情况
//我们先遍历物品，后遍历背包得到的是组合数
//我们先遍历背包，后遍历物品得到的才是排列数
//此题需要我们求的是排列数
/*
for (int i = 0; i < nums.size(); i++) 物品 nums[1,2,5]
for (int j = 0; j <= target; j++) 背包
先遍历物品，则先1后2，先将1放入，在背包里面进行遍历，然后才把2放进来，在背包里面遍历一遍
我们只会出现1,2这种情况，不会出现2,1这种情况
for (int j = 0; j <= target; j++) 背包
for (int i = 0; i < nums.size(); i++) 物品
我们的背包，每一个容量下，都是在1，2的情况下进行遍历的，每个容量下都放了1，2
所以，我们既有1,2，也有2,1 物品排序和其重量排序不一致
*/
//eg nums = [1,2], target = 3
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<uint64_t> dp(target + 1);
dp[0] = 1;
for (int j = 0; j <= target; j++) {
for (int i = 0; i < nums.size(); i++) {
if(j >= nums[i]) dp[j] = dp[j] + dp[j - nums[i]];
}
}
return dp[target];
}
};
leetcode 322. 零钱兑换
//dp[j]：从coins中凑成大小为j的容量，所需要的最少硬币的个数
//凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
//所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
//递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
//首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
//考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值dp[0] = 0覆盖。
//所以下标非0的元素都是应该是最大值。
//本题并不强调集合是组合还是排列。
//如果求组合数就是外层for循环遍历物品，内层for遍历背包。
//如果求排列数就是外层for遍历背包，内层for循环遍历物品。
//本题钱币数量可以无限使用，那么是完全背包。所以遍历的内循环是正序。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<uint64_t> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};
leetcode 279. 完全平方数
//dp[j]
//dp[j] = min(dp[j], dp[j - nums[i]] + 1);
class Solution {
public:
int numSquares(int n) {
vector<uint64_t> dp(n + 1, INT_MAX);
dp[0] = 0;
vector<int> nums;
for (int i = 1; i <= pow(n, 0.5); i++) {
nums.push_back(i * i);
}
for (int i = 0; i < nums.size(); i++) {
for (int j = nums[i]; j <= n; j++) {
dp[j] = min(dp[j], dp[j - nums[i]] + 1);
}
}
return dp[n];
}
};
leetcode 139. 单词拆分
//dp[j]表示当前能否用字典中的字符串拼接成字符串s[0-j-1]，若能拼接dp[j] == true，否则为false，这里的j代表的是长度
//判断dp[s.size()]是否为true
//if 从j到i切割下来的子串在我们的wordDoct中，同时dp[j]为true ----> dp[i] = true
//dp[0]需要初始化为true
//dp其他状态默认都是false
//遍历顺序：求排列数，而不是组合数，对物品的顺序是有要求的，所以我们应该先遍历背包，再遍历物品
//for(int i = 1; i <= s.size(); i++)
//for(int j = 0; j < i; j++) 这里需要做一个截取的操作，j一定要小于i，i是背包的容量，我们要截取的[j,i]这段才是我们需要判断的物品
//物品，我们需要判断是否出现在字典里
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); //substr(起始位置，截取的长度) word是我们截取的物品
if (wordSet.find(word) != wordSet.end() && dp[j]) { //物品在我们的字典里，并且dp[j] == true
dp[i] = true;
}
}
}
return dp[s.size()];
}
};
采用回溯处理，超时代码
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
bool res = false;
backTracking(0, s, wordSet, res);
return res;
}
void backTracking(int startIndex, string s, unordered_set<string>& wordSet, bool& res) {
if (startIndex >= s.size()) {
res = true;
return;
}
for (int i = startIndex; i < s.size(); i++) {
string st = s.substr(startIndex, i - startIndex + 1);
if (wordSet.find(st) != wordSet.end()) {
backTracking(i + 1, s, wordSet, res);
}
else {
continue;
}
}
}
};
递归的过程中有很多重复计算，可以使用数组保存一下递归过程中计算的结果。
这个叫做记忆化递归。
使用memory数组保存每次计算的以startIndex起始的计算结果，如果memory[startIndex]里已经被赋值了，直接用memory[startIndex]的结果。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> memory(s.size(), true);
return backTracking(0, s, wordSet, memory);
}
bool backTracking(int startIndex, string s, unordered_set<string>& wordSet, vector<bool>& memory) {
if (startIndex >= s.size()) {
return true;
}
// 如果memory[startIndex]不是初始值了，直接使用memory[startIndex]的结果
if (!memory[startIndex]) return memory[startIndex];
for (int i = startIndex; i < s.size(); i++) {
string st = s.substr(startIndex, i - startIndex + 1);
if (wordSet.find(st) != wordSet.end()) {
if(backTracking(i + 1, s, wordSet, memory)) return true;
}
else {
continue;
}
}
memory[startIndex] = false; //记录以startIndex开始的子串是不可以被拆分的
return false;
}
};
打家劫舍问题
leetcode 198. 打家劫舍
//dp[i] 考虑下标i，i以及之前的，能偷的最大的金额是dp[i]
//两种状态：偷i房间，nums[i]，因为决定偷i房间，所以我们不能偷i-1房间，则考虑dp[i-2] + nums[i]
//不偷i房间，dp[i-1]
//初始化dp[0]、dp[1]
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0){
return 0;
}
if (nums.size() == 1){
return nums[0];
}
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++){
dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[nums.size()-1];
}
};
leetcode 213. 打家劫舍 II
//dp[i] 考虑下标i，i以及之前的，能偷的最大的金额是dp[i]
//两种状态：偷i房间，nums[i]，因为决定偷i房间，所以我们不能偷i-1房间，则考虑dp[i-2] + nums[i]
//不偷i房间，dp[i-1]
//初始化dp[0]、dp[1]
class Solution {
public:
int robOne(vector<int>& nums) {
if (nums.size() == 0){
return 0;
}
if (nums.size() == 1){
return nums[0];
}
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++){
dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[nums.size()-1];
}
int rob(vector<int>& nums) {
//情况1，不考虑首元素和尾元素
//情况2，不考虑尾元素
//情况3，不考虑首元素
//情况2和3中，都包含了情况1的情况
if (nums.size() == 1) return nums[0];
vector<int> nums1(nums.begin(), nums.end() - 1);
vector<int> nums2(nums.begin() + 1, nums.end());
int res1 = robOne(nums1);
int res2 = robOne(nums2);
return max(res1, res2);
}
};
leetcode 337. 打家劫舍 III (树形dp)
//每个结点只有两个状态，偷这个结点，不偷这个结点
//dp[0]不偷该结点，不偷当前结点所获得的最大金额
//dp[1]偷该结点，偷当前结点所获得的最大金额
//从底部向上去遍历，采用后序遍历的方式，最终是根节点的偷还是不偷两个状态
class Solution {
public:
int rob(TreeNode* root) {
vector<int> result = robTree(root); //result就是我们的dp数组
return max(result[0], result[1]);
}
vector<int> robTree(TreeNode* cur) { //返回当前结点，偷还是不偷，最大的金额数量
if (cur == NULL) {
return vector<int>(2, 0);
}
vector<int> left_dp = robTree(cur->left);
vector<int> right_dp = robTree(cur->right);
//偷当前结点，如果偷当前结点，那么它的左右孩子就一定不能偷了
int value1 = cur->val + left_dp[0] + right_dp[0]; //回溯的时候进行dp，树形dp
//不偷当前结点，考虑是否要偷左右孩子，偷不偷取决于左孩子在偷的情况下和不偷的情况下，最大的钱币数量是多少
int value2 = max(left_dp[0], left_dp[1]) + max(right_dp[0], right_dp[1]);
vector<int> tmp = {value2, value1};
return tmp;
}
};
买卖股票问题
leetcode 121. 买卖股票的最佳时机
//这道题目最直观的想法，就是暴力，找最优间距了。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++){
result = max(result, prices[j] - prices[i]);
}
}
return result;
}
};
//因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。
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;
}
};
//二维dp数组：在第i天，持有这支股票和不持有这支股票。
//dp[i][0] 第i天持有这支股票获取的最大利润 dp[i][1] 第i天不持有这支股票获取的最大利润
//最终要求的结果是max(dp[n-1][0], dp[n-1][1])
//dp[i][0] = dp[i-1][0] (第i-1天也是持有这个股票，这支股票在前几天就购买了) 保持持有的状态
//dp[i][0] = -prices[i] (在第i天的时候，买入这支股票，第i天就持有这个股票了) 状态改变了，第i天买入这支股票，股票只能买卖一次
//dp[i][0] = max(dp[i-1][0], -prices[i]);
//dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]); //第i天的时候把这支股票给卖了，dp[i-1][0]+prices[i]
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
dp[0][0] = 0 - prices[0]; //dp数组初始化
dp[0][1] = 0;
for (int i = 1; i < prices.size(); i++) { //dp数组遍历顺序
dp[i][0] = max(dp[i-1][0], -prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);
}
//其实，我们不持有股票的最大利润，一定比持有股票的最大利润，要多。 return dp[prices.size() - 1][1]就行
return max(dp[prices.size() -1][0], dp[prices.size() - 1][1]);
}
};
leetcode 122 买卖股票的最佳时机 II
//贪心解法
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for(int i = 1; i < prices.size(); i++)
{
result += max(prices[i] - prices[i-1], 0);
}
return result;
}
};
//二维dp数组：在第i天，持有这支股票和不持有这支股票。
//dp[i][0] 第i天持有这支股票获取的最大利润 dp[i][1] 第i天不持有这支股票获取的最大利润
//最终要求的结果是max(dp[n-1][0], dp[n-1][1])
//dp[i][0] = dp[i-1][0] (第i-1天也是持有这个股票，这支股票在前几天就购买了) 保持持有的状态
//dp[i][0] = -prices[i] (在第i天的时候，买入这支股票，第i天就持有这个股票了) 状态改变了，第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]); //第i天的时候把这支股票给卖了，dp[i-1][0]+prices[i]
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
dp[0][0] = 0 - prices[0]; //dp数组初始化
dp[0][1] = 0;
for (int i = 1; i < prices.size(); i++) { //dp数组遍历顺序
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[prices.size() - 1][1]就行
return max(dp[prices.size() -1][0], dp[prices.size() - 1][1]);
}
};
leetcode 714. 买卖股票的最佳时机含手续费
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 max(dp[n - 1][0], dp[n - 1][1]);
}
};
leetcode 309. 最佳买卖股票时机含冷冻期
//dp[i][0] 第i天持有这支股票，获取的最大利润
//dp[i][1] 第i天不持有这支股票，获取的最大利润
//dp[i][2] 第i天不持有这支股票处于冷冻期，，获取的最大利润
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(3, 0));
dp[0][0] = 0 - prices[0];
for (int i = 1; i < prices.size(); i++) {
// 保持之前/开启买入状态
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]); // 如果是开启买入，不能从前一个卖出状态买入，因为有冷冻期，只能从经历了冷冻期的状态买入
// 保持之前/开启卖出状态
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]); // 从前一天的卖出状态进入冷冻期，或继续保持冷冻期
}
// 不需要使用max，因为如果最后一天卖出，那么是卖出位最大
// 如果最后一天是冷冻期，冷冻期位的值来源于前一天的卖出位，当天卖出位也来源于前一天的卖出位
// 所以无论如何都是卖出位是最大值
return dp[prices.size() - 1][1];
}
};
leetcode 123. 买卖股票的最佳时机 III
//dp[i][0] 第i天，不操作
//dp[i][1] 第i天第一次持有这支股票获取的最大利润
//dp[i][2] 第i天第一次不持有这支股票获取的最大利润
//dp[i][3] 第i天第二次持有这支股票获取的最大利润
//dp[i][4] 第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]);
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][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 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];
}
};
leetcode 188. 买卖股票的最佳时机 IV
/*
1、确定dp数组以及下标的含义
使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
j的状态表示为：
0 表示不操作
1 第一次买入
2 第一次卖出
3 第二次买入
4 第二次卖出
除了0以外，偶数就是卖出，奇数就是买入。
题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。
所以二维dp数组的定义为：
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
*/
/*
2、确定递推公式
dp[i][1]，表示的是第i天，持有股票的状态，并不是说一定要第i天买入股票
达到dp[i][1]状态，有两个具体操作：
操作一：第i天买入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
选最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
同理dp[i][2]也有两个操作：
操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
同理可以类比剩下的状态，代码如下：
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]);
}
*/
/*
3、dp数组初始化
第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
第0天做第一次买入的操作，dp[0][1] = -prices[0];
第0天做第一次卖出的操作，这个初始值应该是多少呢？
此时还没有买入，怎么就卖出呢？ 其实大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;
第0天第二次买入操作，初始值应该是多少呢？
第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后在买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。
所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
第二次卖出初始化dp[0][4] = 0;
所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]
代码如下：
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
在初始化的地方同样要类比j为偶数是卖、奇数是买的状态。
*/
/*
4、dp数组遍历顺序
从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
*/
/*
5、举例推导dp数组
最后一次卖出，一定是利润最大的，dp[prices.size() - 1][2 * k]即就是最后求解。
*/
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];
}
};
子序列问题
leetcode 674. 最长连续递增序列
暴力解法
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int res = 1;
for (int i = 0; i < nums.size(); i++) {
int len = 1;
for (int j = i; j < nums.size() - 1; j++) {
if (nums[j] < nums[j+1]) {
len++;
}
else {
break;
}
}
res = max(res, len);
}
return res;
}
};
采用并查集，将不同的连续递增序列放入不同的集合，求出集合元素数目最多的就是最长连续递增序列。
class Solution {
class UnionFind
{
vector<int> s;
public:
UnionFind(int n) {
s = vector<int>(n, -1);
}
int Find(int idx) {
int i = idx;
while (s[i] >= 0) {
i = s[i];
}
return i;
}
void Union(int idx1, int idx2) {
int p1 = Find(idx1);
int p2 = Find(idx2);
if (p1 == p2) return;
if (s[p1] <= s[p2]) {
s[p1] += s[p2];
s[p2] = p1;
}
else {
s[p2] += s[p1];
s[p1] = p2;
}
}
int GetMaxUnionELeNum() {
int res = INT_MAX;
for (int i = 0; i < s.size(); i++) {
res = min(res, s[i]);
}
return abs(res);
}
};
public:
int findLengthOfLCIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
UnionFind uf(nums.size());
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] < nums[i+1]) {
uf.Union(i, i + 1);
}
}
return uf.GetMaxUnionELeNum();
}
};
//dp[i]表示以nums[i]元素结尾的最长连续递增子序列的长度
//dp[i-1]则表示以nums[i-1]元素结尾的最长连续递增子序列的长度
//子序列的起始位置并没有要求
//if (nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;
//因为这里要求是连续的递增子序列，所以没有必要遍历i之前的每一个元素比较dp[j] + 1了
//dp数组全部初始化为1，每个元素的最长连续递增子序列的长度最少为1
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int result = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > nums[i-1]) {
dp[i] = dp[i-1] + 1;
}
// if nums[i] <= nums[i-1] dp[i]不发生改变
result = max(result, dp[i]);
}
return result;
}
};
leetcode 300. 最长递增子序列
//dp[i]表示所有以nums[i]元素为结尾的递增子序列中最长的递增子序列长度
//dp[i] = max(dp[i], dp[j] + 1) j-->[0, i - 1] dp[i]的值是dp[j]+1中的最大值
//dp初始化：dp[i] = 1，子序列最少是包含nums[i]的，长度至少都是1
//遍历顺序 i 从小到大遍历，需要依赖前面已经计算过的结果，求解更新的dp[i]的值 for(int i = 1; i < nums.size(); i++)
//for (int j = 0; j < i; j++)对于每个确定位置的i，遍历所有的dp[j] + 1的情况，选择出最大的作为dp[i]
//最终的result，则需要在dp[i]中选出最大的递增子序列长度
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int result = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1); //if dp[j] + 1 > dp[i] --> update dp[i]
}
}
result = max(result, dp[i]);
}
return result;
}
};
leetcode 718. 最长重复子数组
暴力解法
//超时代码
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int res = 0;
for (int i = 0; i < nums1.size(); i++) { //两层for循环，分别遍历nums1和nums2子数组的起始位置
for (int j = 0; j < nums2.size(); j++) {
int len = 0;
int tmp1 = i;
int tmp2 = j;
while (tmp1 < nums1.size() && tmp2 < nums2.size()) {
if (nums1[tmp1] == nums2[tmp2]) {
len++;
tmp1++;
tmp2++;
}
else {
break;
}
}
res = max(res, len);
}
}
return res;
}
};
//dp[i][j] 以i-1为结尾的nums1和j-1为结尾的nums2，这两个数组的最长重复子数组长度
//if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
//dp[i][0] dp[0][j] 无意义的状态 初始化为0
//两层for循环，遍历nums1和nums2
//为什么没有定义以i和j为结尾的最长重复子数组？
//因为根据此dp数组的定义对于dp[i][0]进行初始化的时候，需要遍历nums1中的所有元素，和nums2[0]进行对比，如果相等则赋值为1
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int res = 0;
for (int i = 1; i <= nums1.size(); i++) {
for (int j = 1; j <= nums2.size(); j++) {
if (nums1[i-1] == nums2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
res = max(res, dp[i][j]);
}
}
return res;
}
};
class Solution {
// dp[i][j] 表示以下标i结尾的数组1和以下标j结尾的数组2，对应的最长公共子序列的长度。
// if t[i] == t[j] dp[i][j] = dp[i-1][j-1] + 1
// dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
public int longestCommonSubsequence(String text1, String text2) {
char[] arr1 = text1.toCharArray();
char[] arr2 = text2.toCharArray();
int n1 = arr1.length;
int n2 = arr2.length;
int[][] dp = new int[n1][n2];
int res = 0;
for (int i = 0; i < n1; i++) {
if (arr1[i] == arr2[0]) {
while (i < n1) {
dp[i][0] = 1;
res = Math.max(res, dp[i][0]);
i++;
}
break;
}
}
for (int j = 0; j < n2; j++) {
if (arr1[0] == arr2[j]) {
while (j < n2) {
dp[0][j] = 1;
res = Math.max(res, dp[0][j]);
j++;
}
break;
}
}
if (arr1[0] == arr2[0]) dp[0][0] = 1;
else dp[0][0] = 0;
for (int i = 1; i < n1; i++) {
for (int j = 1; j < n2; j++) {
if (arr1[i] == arr2[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
res = Math.max(res, dp[i][j]);
}
}
return res;
}
}
leetcode 1143. 最长公共子序列
//表示两个数组之间元素的状态，采用二维dp数组
//dp[i][j] 以[0,i-1]nums1的数组长度，和[0,j-1]nums2的数组长度，的最长公共子序列长度
//if (nums[i-1] == nums[j-1]) dp[i][j] = dp[i-1][j-1] + 1];
//eg: abce ace 的最长公共子序列长度就是 abc ac 的最长公共子序列长度加1
//dp[i][j] = dp[i][j-1] eg: abc ace 最长公共子序列都为ac
//dp[i][j] = dp[i-1][j] eg: acb aec
//综合以上两种情况，故if (nums[i-1] != nums[j-1]) dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
//dp的初始化 dp[i][0]和dp[0][j]初始化为0
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
int res = 0;
for (int i = 1; i <= text1.size(); i++) {
for (int j = 1; j <= text2.size(); 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]);
}
res = max(res, dp[i][j]);
}
}
return res;
}
};
leetcode 1035. 不相交的线（同最长公共子序列）
//同leetcode 1143. 最长公共子序列
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int res = 0;
for (int i = 1; i <= nums1.size(); i++) {
for (int j = 1; j <= nums2.size(); j++) {
if (nums1[i-1] == nums2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
res = max(res, dp[i][j]);
}
}
return res;
}
};
leetcode 53. 最大子数组和
//用分治法来做
class Solution {
public:
int CrossSubArray(vector<int>& A, int low, int mid, int high) {
int leftMaxVal = INT_MIN;
int Sum = 0;
for (int i = mid; i >= low; i--) {
Sum += A[i];
if (Sum > leftMaxVal) {
leftMaxVal = Sum;
}
}
int rightMaxVal = INT_MIN;
Sum = 0;
for (int i = mid + 1; i <= high; i++) {
Sum += A[i];
if (Sum > rightMaxVal) {
rightMaxVal = Sum;
}
}
return leftMaxVal + rightMaxVal;
}
int MaxSubArray(vector<int>& A, int low, int high) {
if (low == high) { //递归到解决到剩下最后一个元素时，最大子数组的值就是该元素的值
return A[low];
}
int mid = (low + high) / 2;
int leftSum = MaxSubArray(A, low, mid);
int rightSum = MaxSubArray(A, mid + 1, high);
int crossSum = CrossSubArray(A, low, mid, high);
if (leftSum >= rightSum && leftSum >= crossSum) return leftSum;
else if (rightSum >= leftSum && rightSum >= crossSum) return rightSum;
else return crossSum;
}
int maxSubArray(vector<int>& nums) {
return MaxSubArray(nums, 0, nums.size()-1);
}
};
//dp[i]定义为以nums[i]结尾的子数组的最大连续子序列的和
//dp[i] = dp[i-1] + nums[i]; 延续前面已经计算过的子序列和
//eg: 0 4 -3 ----> 0 4 -3 2
//dp[i] = nums[i]; 不延续前面的子序列和，从当前位置从头计算
//eg: 0 3 -4 -----> 0 3 -4 2
//故：dp[i] = max(dp[i-1] + nums[i], nums[i]);
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int res = INT_MIN;
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i-1] + nums[i], nums[i]);
res = max(res, dp[i]); //这里没有处理比较dp[0]
}
res = max(res, dp[0]);
return res;
}
};
leetcode 392. 判断子序列
//给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
//字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
//例如，"ace"是"abcde"的一个子序列，而"aec"不是
//dp[i][j]以i-1为尾的字符串s和以j-1为尾字符串t的相同子序列的长度
//if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1
//如果这两个字符串不相同，我们只能在t这个字符串里面删除元素，如果s[i-1] != t[j-1]，我们就相当于将该元素删除掉了
//删除掉我们就考虑j-1前面的字符串和你这个i-1完整这个字符串的相同子序列长度。
//else dp[i][j] = dp[i][j-1]
//dp数组初始化，推导方向：从(i-1,j-1)或者(i,j-1)递推到dp[i][j]
//dp[i][0]和dp[0][j]初始化，无意义初始化为0
//dp数组的遍历顺序，从左到右，从上到下
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0));
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); 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];
}
}
}
if (dp[s.size()][t.size()] == s.size()) {
return true;
}
else {
return false;
}
}
};
leetcode 115. 不同的子序列
//求s里面有多少个像t这样的子序列，就是s字符串中有多少种删除元素的方式，使s可以变成t，那么我们要输出这种方式
//dp[i][j]以i-1为尾的字符串s中有多少个以j-1为尾的字符串t的个数
//if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
//使用s[i-1]和不使用s[i-1]的情况
//s: bagg t : bag 此时s[3] == t[2]，也就是说使用了我们的s3，但是我们的s3也可以不考虑，也就是说模拟把这个s3删除掉，s[2] == t[2]
//else dp[i][j] = dp[i-1][j] (不考虑使用s[i-1]的情况)
//dp[i][0]和dp[0][j]初始化
//dp[i][0]是在字符串s中寻找空字符串的方法，也就是将s中的所有元素全部删除就变成空了，只有一种方法，初始化为1
//dp[0][j]初始化为0
//dp[0][0] = 1
//dp数组的遍历顺序
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size()+1, vector<uint64_t>(t.size()+1, 0));
for (int i = 0; i <= s.size(); i++) {
dp[i][0] = 1;
}
for (int j = 0; j <= t.size(); j++) {
dp[0][j] = 0;
}
dp[0][0] = 1;
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); 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[s.size()][t.size()];
}
};
leetcode 516. 最长回文子序列
给定一个字符串 s，找到其中最长的回文子序列的长度。
-
定义状态：
dp[i][j]表示字符串s的第i到第j个字符之间的最长回文子序列的长度。
-
状态转移方程：
- 如果
s[i] == s[j]，则dp[i][j] = dp[i+1][j-1] + 2。 - 否则，
dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
- 如果
-
初始化：
dp[i][i] = 1，因为单个字符是一个长度为 1 的回文子序列。
-
结果：
dp[0][n-1]，其中n是字符串s的长度。
class Solution {
// 定义状态：dp[i][j]表示字符串s的第i个到第j个字符之间的最长回文子序列的长度
// 状态转移方程：if s[i] == s[j] dp[i][j] = dp[i+1][j-1] + 2
// else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
// 初始化 dp[i][i] = 1
// 结果 dp[0][n-1]
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 从i+1 --> i 则i逆序 从j-1 --> j 则j正序
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
}
class Solution {
public int longestPalindromeSubseq(String s) {
char[] chs = s.toCharArray();
int n = chs.length;
return dfs(0, n - 1, chs);
}
private int dfs(int i, int j, char[] s) {
if (i > j) {
return 0; // 空串
}
if (i == j) {
return 1; // 只有一个字母
}
if (s[i] == s[j]) {
return dfs(i + 1, j - 1, s) + 2; // 都选择
}
return Math.max(dfs(i + 1, j, s), dfs(i, j - 1, s)); // 枚举哪个不选
}
}
class Solution {
public int longestPalindromeSubseq(String s) {
char[] chs = s.toCharArray();
int n = chs.length;
int[][] memo = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
return dfs(0, n - 1, chs, memo);
}
private int dfs(int i, int j, char[] s, int[][] memo) {
if (i > j) {
return 0; // 空串
}
if (i == j) {
return 1; // 只有一个字母
}
if (memo[i][j] != -1) { // 之前计算过
return memo[i][j];
}
if (s[i] == s[j]) {
memo[i][j] = dfs(i + 1, j - 1, s, memo) + 2; // 都选择
return memo[i][j];
}
return memo[i][j] = Math.max(dfs(i + 1, j, s, memo), dfs(i, j - 1, s, memo)); // 枚举哪个不选
}
}
leetcode 5. 最长回文子串
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = findPalindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = findPalindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
// 区分l和r为中心主要处理，abba和aba这种问题。
public String findPalindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}
}
leetcode 72. 编辑距离
class Solution {
// 定义状态：`dp[i][j]` 表示将 `word1` 的前 `i` 个字符转换成 `word2` 的前 `j` 个字符所需的最少操作次数。
// 状态转移方程：如果 `word1[i-1] == word2[j-1]`，则 `dp[i][j] = dp[i-1][j-1]`。
// 否则，`dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`。
// 初始化：`dp[0][j] = j`，表示将空字符串转换为 `word2` 的前 `j` 个字符需要 `j` 次插入操作。
// `dp[i][0] = i`，表示将 `word1` 的前 `i` 个字符转换为空字符串需要 `i` 次删除操作。
// 结果：`dp[m][n]`，其中 `m` 和 `n` 分别是 `word1` 和 `word2` 的长度。
public int minDistance(String word1, String word2) {
char[] w1 = word1.toCharArray();
char[] w2 = word2.toCharArray();
int n1 = w1.length;
int n2 = w2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 0; i <= n1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= n2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (w1[i-1] == w2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
// dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
int minValue = Math.min(dp[i-1][j], dp[i][j-1]);
minValue = Math.min(minValue, dp[i-1][j-1]);
dp[i][j] = minValue + 1; // 插入or替换
}
}
}
return dp[n1][n2];
}
}
扫一扫
533
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
