概述
目录
线性DP
股票系列
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
123. 买卖股票的最佳时机 III
309. 最佳买卖股票时机含冷冻期
其他系列
百度笔试题
1143. 最长公共子序列
53. 最大子数组和
被K整除的最大子数组
最长递增子序列
Leetcode 类似题型 152. 乘积最大子数组
Leetcode 类似题型 221. 最大正方形
最长公共子序列
32. 最长有效括号
10. 正则表达式匹配
64. 最小路径和
198. 打家劫舍
72. 编辑距离
96. 不同的二叉搜索树
139. 单词拆分
字节跳动高频题——圆环回原点问题
5. 最长回文子串
区间DP
312. 戳气球
背包DP
经典背包问题
518. 零钱兑换 II
279. 完全平方数
322. 零钱兑换
416. 分割等和子集
494. 目标和
树状DP
337. 打家劫舍 III
线性DP
股票系列
总结：根据题意确定好股票的状态，列出状态转移方程即可
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：输入：prices = [7,6,4,3,1]
输出：0
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int maxProfit_dp(vector<int>& prices) {
if (prices.size() == 0)
return 0;
//dp[i]在[0--i]天交易取得的最大值
int dp[prices.size()] = {0}, min = prices[0];
for(int i = 1; i < prices.size(); i++)
{
dp[i] = dp[i - 1] > prices[i] - min ? dp[i - 1] : prices[i] - min;
min = min < prices[i] ? min : prices[i];
}
return dp[prices.size() - 1];
}
int maxProfit_greedy(vector<int>& prices) {
//记录最低价格，若当前价格大于最低价格，说明可以交易
//否则则更新最低价格
int min_price = prices[0], ans = 0;
for(int i = 1; i < prices.size(); i++){
if(prices[i] > min_price)
//卖出股票
ans = max(ans, prices[i] - min_price);
else
//更新最低价
min_price = prices[i];
}
return ans;
}
};122. 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
//贪心算法在局部最低买入，在局部最高卖出
//实际上是在所有涨价期间买入卖出即可
int sum = 0;
for(int i = 1; i < prices.size(); i++){
if(prices[i] > prices[i-1])
sum += (prices[i] - prices[i-1]);
}
return sum;
}
int maxProfit_dp(vector<int>& prices) {
/*动态规划解法：
dp[i][0]：在第i天交易完成之后持有股票的最大收入
dp[i][1]：在第i天交易完成之后没有股票的最大收入
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + nums[i])//前一天本身就没有股票或者当天卖了股票之后没有股票
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - nums[i])//前一天本身就有股票或者当天买入股票
*/
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = -prices[0], dp[0][1] = 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]);
}
return max(dp[n-1][0], dp[n-1][1]);
}
};123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：输入：prices = [1]
输出：0
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
/*拆分为两个动态规划问题
dp1[i]：第一次交易获取的最大值(第[0,i]天)
dp1[i] = max(max_profit, price[i]-min_price)
max_profit = max(dp1[i], max_profit)
min_price = min(min_price, price[i])
dp2[i]：第二次交易获取的最大值(倒过来看从第i天到最后一天的最大利润)
dp2[i] = max(max_profit, max_price - price[i])
max_profit = max(dp2[i], max_profit)
max_price = max(max_price, price[i])
res = max(dp1+dp2)[i]
*/
int n = prices.size();
vector<int> dp1(n, 0);
vector<int> dp2(n, 0);
int max_profit = INT_MIN, min_price = prices[0], max_price = prices[n-1];
for(int i = 0; i < n; i++){
dp1[i] = max(max_profit, prices[i]-min_price);
max_profit = max(max_profit, dp1[i]);
min_price = min(min_price, prices[i]);
}
max_profit = INT_MIN;
for(int i = n-1; i >= 0; i--){
dp2[i] = max(max_profit, max_price-prices[i]);
max_profit = max(max_profit, dp2[i]);
max_price = max(max_price, prices[i]);
}
max_profit = INT_MIN;
for(int i = 0; i < n; i++)
max_profit = max(max_profit, dp1[i]+dp2[i]);
return max_profit;
}
int maxProfit_dp(vector<int>& prices) {
/*
另解
dp[i][j]：i代表天数、j代表状态后所剩金额最大值
每个状态表示的都是到目前为止的状态
0:到目前为止无任何交易
dp[i][0] = dp[i-1][0]
1:买入第一支股票的状态：前一天就买入了或者现在买入
dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
2:卖出第一支股票：现在卖出的，前一天就卖出了
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
3:买入第二支股票：前一天就买入了或者现在买入
dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
4:卖出第二支股票：前一天就卖出或者现在卖出
dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
*/
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(5, 0));
dp[0][1] = -1 * prices[0];
dp[0][3] = dp[0][1];
for(int i = 1; i < n; 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[n-1][4];
}
};309. 最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:输入: prices = [1]
输出: 0
一些题解思路：根据题目可知，如果采用动态规划的话，肯定要枚举第i天的一些状态（买入、卖出、是否冻结等等），同时第i天的状态肯定又能用第i-1天的状态来表示。
class Solution {
public:
int maxProfit(vector<int>& prices) {
/**动态规划：多个状态，上一次选择的一些状态会构成本次操作的一些状态
dp[i][0]:拥有股票=max(dp[i-1][0], dp[i-1][2]-nums[i]) 维持上一天拥有或者在今天买入
dp[i][1]:不拥有股票，且接下来处于冷冻期=dp[i-1][0]+nums[i] 今天必须卖出股票
dp[i][2]:不拥有股票，且接下来不是冷冻期=max(dp[i-1][2], dp[i-1][1])
同时可以对状态进行压缩
**/
vector<vector<int>> dp(2, vector<int>(3, 0));
dp[0][0] = -prices[0];
for(int i = 1; i < prices.size(); i++){
dp[1][0] = max(dp[0][0], dp[0][2]-prices[i]);
dp[1][1] = dp[0][0] + prices[i];
dp[1][2] = max(dp[0][2], dp[0][1]);
dp[0][0] = dp[1][0];
dp[0][1] = dp[1][1];
dp[0][2] = dp[1][2];
}
return max(dp[1][0], max(dp[1][1], dp[1][2]));
}
};其他系列
百度笔试题
#include "bits/stdc++.h"
using namespace std;
// # 百度12号第二题
# define MAX_VAL 10000000
int main(){
int N;
cin >> N;
int total = N;
vector<int> vec_a;
while(total--){
int a;
cin >> a;
vec_a.push_back(a);
}
vector<int> vec_b;
total = N;
while(total--){
int a;
cin >> a;
vec_b.push_back(a);
}
/*
动态规划：dp[i][0]：不对nums[i]进行魔法变换的最大操作次数
dp[i][1]：对nums[i]进行魔法变换的最大操作次数
dp[i][0] = dp[i-1][0] iff : nums_a[i] > nums_a[i-1]
= dp[i-1][1] iff : nums_a[i] > nums_b[i-1]
取最小值
dp[i][1] = dp[i-1][0] + 1 iff : nums_b[i] > nums_a[i-1]
= dp[i-1][1] + 1 iff : nums_b[i] > nums_b[i-1]
取最小值
*/
vector<vector<int>> dp(N, vector<int>(2, MAX_VAL));
dp[0][1] = 1;
dp[0][0] = 0;
for(int i = 1; i < N; i++){
if(vec_a[i] > vec_a[i-1])
dp[i][0] = min(dp[i][0], dp[i-1][0]);
if(vec_a[i] > vec_b[i-1])
dp[i][0] = min(dp[i][0], dp[i-1][1]);
if(vec_b[i] > vec_a[i-1])
dp[i][1] = min(dp[i][1], dp[i-1][0]+1);
if(vec_b[i] > vec_b[i-1])
dp[i][1] = min(dp[i][1], dp[i-1][1]+1);
}
int num = min(dp[N-1][0], dp[N-1][1]);
if (num == MAX_VAL)
cout << -1 << endl;
else
cout << num << endl;
}1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
/*dp[i][j]:text1[0:i]与text2[0:j]的最长公共子序列长度
dp[i][j] = dp[i-1][j-1] + 1 , iff : text1[i] == text2[j]
= max(dp[i-1][j], dp[i][j-1]) + 1 , iff text1[i] != text2[j]
*/
if(text1.length() == 0)
return text2.length();
if(text2.length() == 0)
return text1.length();
int len1 = text1.length(), len2 = text2.length();
vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
for(int i = 1; i <= len1; i++)
for(int j = 1; j <= len2; j++){
if(text1[i-1] == text2[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[len1][len2];
}
};
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：输入：nums = [1]
输出：1
示例 3：输入：nums = [5,4,-1,7,8]
输出：23
变形：在子数组中奇数位置为其本身，偶数位置为其相反数
dp[i][0]：以nums[i]为子数组的结尾数据，且其作为奇数下标的最大连续子数组和
dp[i][1]：以nums[i]为子数组的结尾数据，且其作为偶数下标的最大连续子数组和
dp[i][0] = max(nums[i], dp[i-1][1]+nums[i])
dp[i][1] = max(0, dp[i-1][0]-nums[i])//0表示不选自然作为候选子数组的偶数下标
被K整除的最大子数组
最长递增子序列
dp[i]表示以nums[i]结尾的子序列的最大长度
则dp[i] = max(dp[j] + 1) for j in [0...i-1] and nums[i] >= nums[j]
maxlen = max(dp[i]) for i in [0...nums.length()]
最长递增列另解：线段树
对于当前第i个元素，需搜索比第i个元素小的元素中的最长子序列，搜索时间为O(n)。如何减少查询的时间成为需要解决的问题。如若有两个元素x和y，若x<y，且以元素x结尾的最长子序列长度大于以元素y结尾的子序列长度，那么元素y其实是可以被删除的，因为比元素y小的元素x显然有机会在后续构成一个更长的子序列。那么元素的大小和以该元素结尾的子序列长度都是逐渐增加的。那么当扫描到当前某个元素时，使用二分查找其需要被放入的位置，路径长度等于其左侧元素的子序列长度+1，并删除右侧元素（因为右侧元素比当前元素大，但构成的子序列的长度一样）。
由于子序列长度数组是逐个递增的，在这里其实只需要使用一个数组d[i]表示所有长度为i的递增子序列的末尾元素的最小值，引入一个变量len记载目前得到的最长子序列的长度。当扫描到某个元素item时，若该元素item大于d[len]：则d[++len]=item；否则：则在数组d中找到第一个大于item的位置j,并修改位置j的值：d[j]=item（因为元素item小于d[j],所以d[j]要被替换）。由于该数组是递增的，第二种情况搜索时可以使用二分搜索，所以算法的复杂度为O(nlogn)。
int lengthOfLIS_nlogn(vector<int>& nums) {
/*使用线段树思想求解.O(nlogn)
假设对于两个元素x<y，以元素x结尾的递增子串长度和以元素y结尾的递增子串相等
那我们应该选择元素x，而不是元素y，因为选择元素x后面可以递增的元素更多，子串可以变地更大
引入一个数组d[i]表示长度为i的递增子串中，末尾元素最小的那个
数组d的元素是严格递增的
*/
vector<int> d(nums.size()+1, -100000);
int length = 0;
int low, high, index;
for(auto const& num: nums){
if(num > d[length]){
//元素大于目前d数组的最大元素，直接插入
length += 1;
d[length] = num;
}else{
//在d数组的中间，需要二分搜索
low = 1, high = length;
index = 1;//d[k]第一次大于num的元素的位置，若所有元素都比num大，则应该在index = 1处更新元素
while(low <= high){
int middle = (low + high) >> 1;
if(d[middle] >= num){
//找到第一次大于num的位置，
//例如dp:1 3 5 ，现在来了个3，3应该被替换到3的位置而不是5的位置，若是5维持的不是严格递增（非递减），若是3维持的才是严格递增
//为什么要将等于号放到此处，相当于等于时不需要更新当前值，所以实际情况应该把当前扫描元素d[middle]当作大于num来处理
high = middle - 1;
index = middle;
}else{
low = middle + 1;
}
}
d[index] = num;
}
for(int i = 0; i <= length; i++){
cout << d[i] << " ";
}
cout << endl;
}
return length;
}Leetcode 类似题型 152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
class Solution {
public:
int maxProduct(vector<int>& nums) {
/*这一题能够联想到最长递增子序列求解，即dp[i]表示以元素nums[i]结尾连续子数组的构成的最大值
dp[i] = max(dp[i-1]*nums[i], nums[i])
但在给定的数组中有负数，所以不能按照这个思路来求解，有可能负负为正，导致当前值更大
引入两个动规数组dp_max[i]以及dp_min[i]
考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，并且希望它尽可能地大。
*/
vector<int> dp_max(nums.size(), 0);
vector<int> dp_min(nums.size(), 1e6);
dp_max[0] = nums[0];
dp_min[0] = nums[0];
for(int i = 1; i < nums.size(); i++){
dp_min[i] = get_min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i]);
dp_max[i] = get_max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i]);
}
int max_out = -10;
for(const auto &x: dp_max){
max_out = max_out > x ? max_out : x;
}
return max_out;
}
int get_min(int a, int b, int c){
int temp;
temp = a < b ? a : b;
temp = temp < c ? temp : c;
return temp;
}
int get_max(int a, int b, int c){
int temp;
temp = a > b ? a : b;
temp = temp > c ? temp : c;
return temp;
}
};Leetcode 类似题型 221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：输入：matrix = [["0"]]
输出：0
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
/*
动态规划：dp[i][j]：以matrix[i][j]为右下角所构成的正方形
dp[i][j] <= min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
dp[i][j] >= min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
故：dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
*/
vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size()));
int max_val = 0;
for(int i = 0; i < matrix.size(); i++)
for(int j = 0; j < matrix[0].size(); j++){
if(i == 0 || j == 0){
if(matrix[i][j] == '0')
dp[i][j] = 0;
else
dp[i][j] = 1;
}else if(matrix[i][j] == '0'){
dp[i][j] = 0;
}else{
dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
}
max_val = max(max_val, dp[i][j]);
}
return max_val * max_val;
}
};最长公共子序列
假设两段字符串分别为s1, s2
dp[i][j]表示s1[0: i]与s2[0: j]的最长公共子串
现在需要考察s1[i]与s2[j]
1.若s1[i] == s2[j]
dp[i][j] = dp[i-1][j-1] + 1;
2.若s1[i] != s2[j]:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
class Solution {
public:
int longestValidParentheses(string s) {
/*动规求解
dp[i]表示s[0:i]构成的最长有效括号子串的长度
分情况讨论即可：
1.s[i] == '('
dp[i] = 0
2.s[i] == ')'
继续分情况讨论
s[i-1] == '(': dp[i] = dp[i-2] + 2
s[i-1] == ')': if s[i-1-dp[i-1]] == '(' dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]]
现在要讨论s[i-1]的右括号在前面可以配对的左括号
(i-1-dp[i-1]+1)前面(i-1-dp[i-1])是否继续存在一个左括号与当前的右括号配对，
( ( ***************** ) )
i-1-dp[i-1] i-1-dp[i-1]+1 i-1 i
该左括号的位置为i-1-dp[i-1]
*/
int dp[s.length()], maxlen = 0;
memset(dp, 0, sizeof(dp));
for(int i = 1; i < s.length(); i++){
if(s[i] == ')'){
if(s[i-1] == '('){
dp[i] = 2;
if(i-2 >= 0){
dp[i] = dp[i] + dp[i-2];
}
}
else if(dp[i-1] > 0){
if(i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '('){
dp[i] = dp[i-1] + 2;
if(i-2-dp[i-1] >= 0){
dp[i] = dp[i] + dp[i-2-dp[i-1]];
}
}
}
}
maxlen = max(maxlen, dp[i]);
}
return maxlen;
}
};10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
一些参考的题解思路：在对模式串为*时，弄清楚应该是如果当前模式串能够匹配上的话，应该丢掉字符串当前匹配上的那个字符，继续往前匹配即可。
class Solution {
public:
bool match(char a, char b){
//a为s中的字符，b为p中的字符
if(b == '.')
return true;
return a == b;
}
bool isMatch(string s, string p) {
/*
dp[i,j]表示模式规律串p[0:j-1]能否完整匹配字符串s[0:i-1]
分以下几种情况来讨论模式规律串p的最后一个字符：
1.p的当前字符为小写字母a-z:
dp[i][j] = dp[i-1][j-1] iff s[i] == p[j]
dp[i][j] = false;
2.p的当前字符为*:
若s[i] == p[j-1] or p[j-1] == . : 说明模式规律串p和给定字符串s能匹配上，匹配0次或1次
dp[i][j] = dp[i][j-2] or dp[i-1][j]
若s[i] != p[j-1]: 说明模式规律串p不能和给定字符串s能匹配上比如(ab, abc * )。
遇到 * 往前看两个，发现前面 s[i] 的 ab 对 p[j-2] 的 ab 能匹配，虽然后面是 c*，但是可以看做匹配 00 次 c，相当于直接去掉 c *，所以也是 True。
dp[i][j] = dp[i][j-2]
3.p的当前字符为.:
dp[i][j] = dp[i-1][j-1]
*/
if(s.length() == 0 || p.length() == 0)
return false;
bool dp[31][31];
for(int i = 0; i < 31; i++)
dp[i][0] = false;
for(int j = 0; j < 31; j++)
dp[0][j] = false;
dp[0][0] = true;
for(int i = 1; i <= s.length(); i++)
for(int j = 1; j <= p.length(); j++){
if(p[j-1] == '*'){
dp[i][j] = dp[i][j-2];
if(match(s[i-1], p[j-2])) dp[i][j] |= dp[i-1][j];
}
else{
if(match(s[i-1], p[j-1])) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = false;
}
}
return dp[s.length()][p.length()];
}
};64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
//动态规划实现最小路径的求解
int dp[grid[0].size()];
dp[0] = grid[0][0];
for(int i = 0; i < grid.size(); i++)
for(int j = 0; j < grid[0].size(); j++){
if(i == 0 && j == 0)
continue;
else if(i == 0){
dp[j] = dp[j-1] + grid[i][j];
}
else if(j == 0){
dp[j] += grid[i][j];
}
else
dp[j] = min(dp[j-1], dp[j]) + grid[i][j];
}
return dp[grid[0].size() - 1];
}
};198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int rob(vector<int>& nums) {
/*
动态规划实现：dp[i]表示区间[0-i]能够被偷窃的最高金额
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
疑惑第i-1天可能没有获取物品，那么dp[i] = dp[i-1] + nums[i]等效于
dp[i] = dp[i-2] + nums[i]
*/
vector<int> dp(nums.size()+1, 0);
dp[1] = nums[0];
for(int i = 1; i < nums.size(); i++){
dp[i+1] = max(dp[i], dp[i-1]+nums[i]);
}
return dp[nums.size()];
}
int rob_twodim(vector<int>& nums) {
//二维DP相关
/*
dp[i][0]：今天打劫获得的最高金额
dp[i][1]:不打劫获得的最高金额
dp[i][0] = dp[i-1][1] + nums[i]
dp[i][1] = max(dp[i-1][1], dp[i-1][0])
*/
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = nums[0];
for(int i = 1; i < n; i++){
dp[i][0] = dp[i-1][1] + nums[i];
dp[i][1] = max(dp[i-1][1], dp[i-1][0]);
}
return max(dp[n-1][0], dp[n-1][1]);
}
};72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
class Solution {
public:
int minDistance(string word1, string word2) {
/*dp[i][j]表示字符串word1[1:i]转换成word2[1:j]的最小次数
这里需要注意到dp[i][j]的来源有三：
1.dp[i][j-1]+1，对于字符串word2[1:j-1]继续添加一个字符即可
2.dp[i-1][j]+1，对于字符串word1[1:i-1]继续添加一个字符即可
3.dp[i-1][j-1]，对于字符串word1[1:i-1]或者说word2[1:j-1]添加一个字符即可完成（若相等则不需要）
*/
if(word1.size() == 0 || word2.size() == 0)
return word1.size() + word2.size();
int dp[word1.size()+1][word2.size()+1];
for(int i = 0; i <= word1.size(); i++)
dp[i][0] = i;
for(int j = 0; j <= word2.size(); j++)
dp[0][j] = j;
for(int i = 1; i <= word1.size(); i++)
for(int j = 1; j <= word2.size(); j++){
int tmp = dp[i-1][j-1];
if(word1[i-1] != word2[j-1])
tmp += 1;
dp[i][j] = min(tmp, min(dp[i][j-1], dp[i-1][j]) + 1);
}
return dp[word1.size()][word2.size()];
}
};96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：输入：n = 1
输出：1
class Solution {
public:
int numTrees(int n) {
/*
用一个类似于动态规划的思想，G(n)表示长度为n的序列能够构成的二叉搜索树的种数
F(i,n)表示以根为i长度为n构成的二叉搜索树的种数
G(n) = sigmai = 1 - n : F(i, n)
F(i, n)又可以由长度为i-1的左子树以及n-i的右子树构成，两者直接相乘
即被表示为 G(i-1) * G(n-i)
*/
vector<int> G(n+1, 0);
G[0] = 1; //表示没有树结构
G[1] = 1; //表示只有一个节点
for(int i = 2; i <= n; i++)
for(int j = 1; j <= i; j++){
G[i] += G[j-1] * G[i-j];
}
return G[n];
}
};139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
//动态规划：dp[i]表示字符串的前i个字符能否拆分成wordDict
//对于当前第i个字符，向前枚举字符(i-j+1:i)是否在wordDict中，这样dp[i] = dp[i-j+1]
bool dp[s.size()+1];
memset(dp, 0, s.size()+1);
set<string> word_set(wordDict.begin(), wordDict.end());
int max_len = 0, min_len=1e6;
for(auto const&word: word_set){
if(word.length() < min_len) min_len = word.length();
if(word.length() > max_len) max_len = word.length();
}
dp[0] = true;
for(int i = 1; i <= s.size(); i++){
for(int j = min_len; j <= max_len; j++){
int index = i - j;
//此处的index指向dp数组，对应于字符串而言应该是index-1，我们要提取的是字符串是下一位
//即index-1+1，故s.substr(index, j)
if(index >= 0 && word_set.count(s.substr(index, j))){
//枚举的中间的字符串(index, j)被包含在其中
dp[i] = dp[index];
}
if(dp[i]) break;
}
}
return dp[s.size()];
}
};字节跳动高频题——圆环回原点问题
圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
输入: 2 输出: 2 解释：有2种方案。分别是0->1->0和0->9->0
本题考察的是动态规划。
如果你之前做过leetcode的70题爬楼梯，则应该比较容易理解：走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。
因此，若设dp[i][j]为从0点出发走i步到j点的方案数，则递推式为：
ps:公式之所以取余是因为j-1或j+1可能会超过圆环0~9的范围
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
class Solution {
public:
string longestPalindrome(string s) {
//动态规划
/*
dp[i][j]:s[i-j]能否构成回文子串
*/
int n = s.length();
int max_len = 1, left = 0, right = 0;
vector<vector<bool>> dp(n, vector<bool>(n, false));
for(int i = 0; i < n; i++)
dp[i][i] = true;;
for(int i = 0; i < n-1; i++){
if(s[i] == s[i+1]){
dp[i][i+1] = true;
max_len = 2;
left = i;
right = i+1;
}
}
for(int len = 3; len <= n; len++)
for(int i = 0; i + len - 1 < n; i++){
int j = i + len - 1;
if(s[i] == s[j] && dp[i+1][j-1]){
dp[i][j] = true;
if(len > max_len){
max_len = len;
left = i;
right = j;
}
}
}
return s.substr(left, right-left+1);
}
};区间DP
需要对构成该区间的状态进行枚举，常见解题思路，先枚举区间长度，再枚举区间起始位置，然后对于中间间断点再进行枚举实现动规。
312. 戳气球
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
示例 2：输入：nums = [1,5]
输出：10
class Solution {
public:
int maxCoins(vector<int>& nums) {
/*
区间DP
dp[i][j]表示[i,j]的最大收益，现在讨论i...j如何生成，肯定是由两个已经被戳完的子区间[i...k-1][k+1...j]中戳掉气球k生成
dp[i][j] = max(dp[i][k-1]+dp[k+1][j], nums[i-1]*nums[j+1]*nums[k])
*/
int n = nums.size();
vector< vector<int>> dp(n+2, vector<int>(n+2, 0));
//防止原来的数组越界
nums.insert(nums.begin(), 1);//防止i-1<0越界
nums.push_back(1);//防止j+1>n越界
for(int len = 1; len <= n; len++)
//按长度为len的区间[i,j]进行枚举
for(int i = 1; i + len - 1 <= n; i++){
int j = i + len - 1;
//[i, j]这个区间，k在哪里不确定，需要枚举
for(int k = i; k <= j; k++){
dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]);
}
// cout << len << " " << i << " " << j << " " << dp[i][j] << endl;
}
return dp[1][n];
}
};背包DP
经典背包问题
可参考题目关于背包DP题目链接：背包问题（目录）
01背包：物品只能被选择一次
dp[i][j]：容量为j的情况下选择[0--i]的物品最大价值
选择第i个物品，不选择第i个物品
dp[i][j] = max(dp[i-1][j-wei[i]] + val[i], dp[i-1][j])
for i in wei.size():
for j in (0, n):
dp[i][j] = dp[i-1][j-wei[i]] + dp[i-1][j]
转换成一维：dp[j]：表示容量为j的情况下能够选择的物品的最大价值
（注意容量遍历的顺序需要改变，改为递减遍历）
dp[j] = dp[j-wei[i]] + dp[j]
完全背包：物品能被选择多次
也可以分为两种情况，选择第i个物品和不选择第i个物品
dp[i][j] = max(dp[i][j-wei[i]] + val[i], dp[i-1][j])
dp[i][j-wei[j]]：意味着选择第i个物品之后还可以继续选择，这是和01背包的不同之处
压缩成一维:dp[j] = max(dp[j-wei[i]]+val[i], dp[j])可参考的链接完全背包
518. 零钱兑换 II
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：输入：amount = 10, coins = [10]
输出：1
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int change(int amount, vector<int>& coins) {
/*
01背包：物品只能被选择一次
dp[i][j]：容量为j的情况下选择[0--i]的物品最大价值
选择第i个物品，不选择第i个物品
dp[i][j] = max(dp[i-1][j-wei[i]] + val[i], dp[i-1][j])
for i in wei.size():
for j in (0, n):
dp[i][j] = dp[i-1][j-wei[i]] + dp[i-1][j]
转换成一维：dp[j]：表示容量为j的情况下能够选择的物品的最大价值
（注意容量遍历的顺序需要改变，改为递减遍历）
dp[j] = dp[j-wei[i]] + dp[j]
完全背包：物品能被选择多次
也可以分为两种情况，选择第i个物品和不选择第i个物品
dp[i][j] = max(dp[i][j-wei[i]] + val[i], dp[i-1][j])
dp[i][j-wei[j]]：意味着选择第i个物品之后还可以继续选择，这是和01背包的不同之处
压缩成一维:dp[j] = max(dp[j-wei[i]]+val[i], dp[j])
*/
/*
对于本题不难给出递推方程：dp[i][j]：从0--i硬币中选择在给定容量（总金额）为j的情况下的组合数
选择第i个硬币+不选择第i个硬币
dp[i][j] = dp[i][j-conis[i]] + dp[i-1][j]
继续优化为一个维度
dp[j] = dp[j-coins[i]] + dp[j]
注意：在遍历时，先物品再容量，组合数
先容量再物品，排列数
*/
int n = coins.size();
vector<vector<int>> dp(n, vector<int>(amount+1, 0));
//对第0行初始化
dp[0][0] = 1;
for(int i = coins[0]; i <= amount; i++){
dp[0][i] = dp[0][i-coins[0]];
}
//对第0列初始化，即金额为0时方案数为1
for(int j = 1; j < n; j++)
dp[j][0] = 1;
for(int i = 1; i < n; i++)
for(int j = 1; j <= amount; j++){
//dp[i][j-conis[i]] 选择第i个
//dp[i-1][j] 不选择第i个
dp[i][j] = dp[i-1][j];
if(j-coins[i] >= 0)
dp[i][j] += dp[i][j-coins[i]];
}
return dp[n-1][amount];
}
int change_youhua(int amount, vector<int>& coins) {
vector<int> dp(amount+1, 0);
dp[0] = 1;
for(auto coin: coins)
for(int i = coin; i <= amount; i++){
dp[i] += dp[i-coin];
}
return dp[amount];
}
};279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：输入：n = 13
输出：2
解释：13 = 4 + 9
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
int numSquares(int n) {
/*动态规划，dp[i]表示数i最少由多少个完全平方数表示
dp[i] = 1 + min(dp[i - j^2])(j = 1---sqrt(i))
*/
vector<int> dp(n+1, 0);
for(int i = 1; i <= n; i++){
int num = 10000;
for(int j = 1; j <= sqrt(i); j++){
num = min(num, dp[i-j*j]);
}
dp[i] = 1 + num;
}
return dp[n];
}
};322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：输入：coins = [2], amount = 3
输出：-1
示例 3：输入：coins = [1], amount = 0
输出：0
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
/*
动态规划：dp[i]=min(dp[i-k_j]+1) j = 1..n
*/
vector<int> dp(amount+1, 1e9);
dp[0] = 0;
for(int i = 1; i <= amount; i++){
for(int j = 0; j < coins.size(); j++){
if(i-coins[j] >= 0)
dp[i] = min(dp[i], dp[i-coins[j]]+1);
}
}
return dp[amount] == 1e9 ? -1 : dp[amount];
}
};416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
这道问题是我学习「背包」问题的入门问题，做这道题需要做一个等价转换：是否可以从输入数组中挑选出一些正整数，使得这些数的和 等于 整个数组元素的和的一半。很坦白地说，如果不是我的老师告诉我可以这样想，我很难想出来。容易知道：数组的和一定得是偶数。
本题与 0-1 背包问题有一个很大的不同，即：
0-1 背包问题选取的物品的容积总量 不能超过 规定的总量；
本题选取的数字之和需要 恰好等于 规定的和的一半。解决的基本思路是：物品一个一个选，容量也一点一点增加去考虑，这一点是「动态规划」的思想，特别重要。
class Solution {
public:
bool canPartition(vector<int>& nums) {
/*
dp[i][j]表示从[0----i]中选择一些数使得总和恰好为j
dp[i][j] = dp[i-1][j-nums[i]](选择) or dp[i-1][j](不选择)
*/
int sum = 0;
for(int i = 0; i < nums.size(); i++)
sum += nums[i];
if(sum % 2 == 1)
return false;
sum /= 2;
vector<vector<bool>> dp(nums.size(), vector<bool>(sum+1, false));
for(int i = 0; i < nums.size(); i++){
dp[i][0] = true;//表示和为0：即一个数字也不选择
}
for(int j = 1; j <= sum; j++){
if(j != nums[0]){
dp[0][j] = false;//表示选择第0个数，和为nums[0]
}else
dp[0][j] = true;
}
for(int i = 1; i < nums.size(); i++)
for(int j = 1; j <= sum; j++){
//当前这个数还能选择
if(j >= nums[i]){
dp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j];
}else
dp[i][j] = dp[i-1][j];
}
return dp[nums.size()-1][sum];
}
};494. 目标和
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：输入：nums = [1], target = 1
输出：1
与分割等和子集比较类似，确定转移状态初始值可以自己先演算一下，存储空间的优化
class Solution {
public:
int num;
void dfs(vector<int> nums, int index, int target, int now){
//已经从[0...index-1]中选择了部分元素，now为前面已选择元素的累计和
if(index == nums.size()){
//遍历到最后
if(now == target)
num += 1;
return;
}else{
dfs(nums, index+1, target, now + nums[index]);
dfs(nums, index+1, target, now - nums[index]);
}
}
int findTargetSumWays(vector<int>& nums, int target) {
/*法一：回溯法求解（超时）
法二：动态规划，类似于分割等和数组子集
dp[i][j]表示从[0...i]选择一些数使得和刚好为j的方案的数目
dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j]
dfs(nums, 0, target, 0);
// return num;
继续优化：对存储空间的优化dp[j] = dp[j-nums[i]] + dp[j];
*/
int a, b, total=0;
for(int i = 0; i < nums.size(); i++)
total += nums[i];
if((total + target) % 2 == 1 || total < target)
//不能整除或者小于目标值
return 0;
a = (total + target) / 2;
b = (total - target) / 2;
int n = nums.size();
int m = a < b ? a : b;
if(m < 0)
return 0;
vector<int> dp(m+1, 0);
//初始化
dp[0] = 1;//无元素可以选择，构成的和为0的方案数肯定为1
for(int i = 1; i <= n; i++){
for(int j = m; j >= 0; j--){
if(j >= nums[i-1]){
//能放下当前的数
dp[j] += dp[j-nums[i-1]];
}
}
}
return dp[m];
}
};树状DP
337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
class Solution {
public:
map<TreeNode*, int> f;
map<TreeNode*, int> g;
int rob(TreeNode* root) {
/*
树形DP，在之前的线性DP中的dp[i]变成了某个节点
f(node)表示不选择节点Node的收益最大值
g(node)表示选择节点Node的收益最大值
f(node) = max(f(node->left), g(node->left)) + max(f(node->right), g(node->right))
g(node) = f(node->left) + f(node->right) + node->val
根据状态枚举可以知道，我们必须先知道儿子节点，才能知道其父亲节点的收益，所以应该采取后续遍历（左、右、根）
*/
dfs_initialize(root);//初始化节点
f.insert(pair<TreeNode*, int>(nullptr, 0));
g.insert(pair<TreeNode*, int>(nullptr, 0));
dfs(root);
return max(f[root], g[root]);
}
void dfs_initialize(TreeNode* root){
if(root == nullptr)
return;
f.insert(pair<TreeNode*, int>(root, 0));
g.insert(pair<TreeNode*, int>(root, 0));
dfs_initialize(root->left);
dfs_initialize(root->right);
}
void dfs(TreeNode* root){
//对root展开后续遍历
if(root == nullptr)
return ;
dfs(root->left);
dfs(root->right);
f[root] = max(f[root->left], g[root->left]) + max(f[root->right], g[root->right]);
g[root] = f[root->left] + f[root->right] + root->val;
cout << "now : " << root->val << " f " << f[root] << " g " << g[root] << endl;
}
pair<int, int> dfs_compress(TreeNode* root){
//空间压缩：对root展开后续遍历
if(root == nullptr)
return {0, 0};
auto l = dfs(root->left);
auto r = dfs(root->right);
int f_val, g_val;
f_val = max(l.first, l.second) + max(r.first, r.second);
g_val = l.first + r.first + root->val;
return {f_val, g_val};
}
};相关参考链接：
[力扣] DP问题分类汇总
数据结构与算法 - 动态规划（线性动态规划）
告别动态规划，连刷 40 道题，我总结了这些套路，看不懂你打我（万字长文）
动态规划常见类型总结
最后
以上就是拼搏音响为你收集整理的动态规划归纳线性DP区间DP背包DP树状DP的全部内容，希望文章能够帮你解决动态规划归纳线性DP区间DP背包DP树状DP所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
![[LeetCode]Regular Expression Matching、Wildcard Matching](/uploads/reation/bcimg1.png)
发表评论 取消回复