36 氪 网站如何优化,wordpress带会员中心模板,如何将自己做的网站变成中文,黑龙江建设网官方网站三类人员简介
动态规划最核心两步#xff1a;
状态表示#xff1a;dp[i]代表什么状态转移方程#xff1a;如何利用已有的dp求解dp[i]
只要这两步搞对了#xff0c; 就完成了动态规划的%95 剩下的就是细节问题#xff1a;
dp初始化顺序#xff08;有时是倒序#xff09;处理边…简介
动态规划最核心两步
状态表示dp[i]代表什么状态转移方程如何利用已有的dp求解dp[i]
只要这两步搞对了 就完成了动态规划的%95 剩下的就是细节问题
dp初始化顺序有时是倒序处理边界问题n过小则直接返回避免越界 这是动态规划第一小节 简单介绍下dp主要类型
斐波那契数列模型路径问题简单多状态 dp 问题子数组系列子序列问题回文串问题两个数组的 dp 问题01 背包问题完全背包问题二维费用的背包问题似包非包卡特兰数 一.斐波那契数列模型
1.第N个泰伯纳妾数
link:1137. 第 N 个泰波那契数 - 力扣LeetCode
code
class Solution {
public:int tribonacci(int n) {if(n 0) return n;if(n 1 || n 2) return 1;// 动态规划vectorint dp(n 1, -1);// initdp[0] 0; dp[1] dp[2] 1;for(int i 3; i dp.size();i){dp[i] dp[i - 1] dp[i - 2] dp[i - 3];}return dp[n];}
}; 2.三步问题
link:面试题 08.01. 三步问题 - 力扣LeetCode
code
class Solution {
public:const int MOD 1e9 7;int waysToStep(int n) {// 状态表示dp[n] 表示上n节台阶的方式数// 状态转移dp[n] dp[n - 1] dp[n - 2] dp[n - 3];vectorint dp(n 5 , -1);// init dpdp[1] 1; dp[2] 2; dp[3] 4;if(n 3) return dp[n];for(int i 4; i dp.size(); i){dp[i] ((dp[i - 1] dp[i - 2])%MOD dp[i - 3])%MOD;}return dp[n];}
}; 3.使用最小花费爬楼梯
link:746. 使用最小花费爬楼梯 - 力扣LeetCode
code
class Solution {
public:int minCostClimbingStairs(vectorint cost) {// 状态表示:dp[i]表示爬到第i台阶需要的最小费用/不包括i台阶// 状态转移:dp[i] min(dp[i - 2] cost[i - 2], dp[i - 1] cost[i - 1])vectorint dp(cost.size() 1, -1);// init dpdp[0] dp[1] 0;// dpfor(int i 2; i dp.size(); i){dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[cost.size()];}
}; 4.解码方法
link:91. 解码方法 - 力扣LeetCode
code
class Solution {
public:int numDecodings(string s) {// 状态表示dp[i]表示s[0,i](包含s[i])解码方法总数// 状态转移: dp[i] valid(s[i])?dp[i - 1]:0 valid(s[i-1,i]?dp[i - 2]:0if(s.size() 1){return valid(string(1, s[0])) ? 1 : 0;}if(s.size() 2){return (valid(string(1, s[0])) valid(string(1, s[1]))) valid(s.substr(0, 2));}vectorint dp(s.size(), 0);// init dpdp[0] valid(string(string(1, s[0]))) ? 1 : 0;dp[1] (valid(string(1, s[0])) valid(string(1, s[1]))) valid(s.substr(0, 2));// dpfor(int i 2; i dp.size(); i){dp[i] (valid(string(1, s[i])) ? dp[i - 1] : 0) (valid(s.substr(i-1, 2))?dp[i - 2] : 0);}return dp[s.size() - 1];}bool valid(string s){if(s.size() 1) return s[0] 1 s[0] 9;else// s.size()2{return stoi(s) 10 stoi(s) 26;}}
}; 二.路径问题
5.不同路径
link:62. 不同路径 - 力扣LeetCode
tips:
此问题中 我们可以多开一行和一列从1下标开始初始有效值
这样可以避免状态转移时的下标越界问题
code
class Solution {
public:vectorvectorint dp;int uniquePaths(int m, int n) {// dp[i][j]:从(0, 0)到(i, j)// dp[i][j] dp[i-1][j] dp[i][j-1]dp vectorvectorint(m 5, vectorint(n 5, 0));// dp此时可以不用-1标记是否初始化 因为是按顺序初始化的// init dpdp[0][1] 1;// 间接初始化dp[1][1] 防止for循环覆盖dp[1][1];// dpfor(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][n];}
};
6.不同路径II
link:63. 不同路径 II - 力扣LeetCode code
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint grid) {// dp[i][j]:起点到(i, j)的路径数// dp[i][j] grid[i][j] 1 ? 0 : dp[i-1][j] dp[i][j-1];// 注意dp多开一行和一列 从下标1开始初始化vectorvectorint dp(grid.size() 1, vectorint(grid[0].size() 1, 0));// init dpdp[0][1] 1;// 间接初始化dp[1][1]// dpfor(int i 1; i grid.size(); i){for(int j 1; j grid[0].size(); j){dp[i][j] (grid[i-1][j-1] 1 ? 0 : dp[i-1][j] dp[i][j-1]);}}return dp[grid.size()][grid[0].size()];}
}; 7.珠宝的最高价值
link:LCR 166. 珠宝的最高价值 - 力扣LeetCode
code
class Solution {
public:int jewelleryValue(vectorvectorint frame) {// dp[i][j]:走到(i, j)能拿到的最大珠宝// dp[i][j] max(dp[i-1][j], dp[i][j-1])frame[i][j];// 多开一行一列 从下标1初始化vectorvectorint dp(frame.size() 1, vectorint(frame[0].size() 1, 0));for(int i 1; i dp.size(); i){for(int j 1; j dp[0].size(); j){dp[i][j] max(dp[i-1][j], dp[i][j-1])frame[i-1][j-1];//注意dp和frame下标不一致}}return dp[frame.size()][frame[0].size()];}
}; 8.下降路径最小和
link:931. 下降路径最小和 - 力扣LeetCode
code
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {// dp[i][j]:下降到(i, j)的下降路径最小和// dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j1]) matrix[i][j]// 多开两行两列 从下标1开始初始化// 相当于上下左右都围上了一圈 避免越界vectorvectorint dp(matrix.size()2, vectorint(matrix[0].size()2, INT_MAX));// init dpfor(int i 1; i matrix.size(); i){for(int j 1; j matrix[0].size(); j){if(i1)dp[i][j] matrix[i-1][j-1];else{dp[i][j] matrix[i-1][j-1] min(min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j1]);}}}int ans INT_MAX;for(int col 1; col matrix[0].size(); col){ans min(ans, dp[matrix.size()][col]);}return ans;}
}; 9.最小路径和
link:64. 最小路径和 - 力扣LeetCode
code
class Solution {
public:int minPathSum(vectorvectorint grid) {// dp[i][j]:从左上角到(i,j)的数字总和最小值// dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])// dp多开一行一列 从下标1开始初始化。防止下标越界vectorvectorint dp(grid.size()1, vectorint(grid[0].size()1, INT_MAX));// init dpdp[0][1] 0;// 间接初始化dp[1][1]// dpfor(int i 1; i grid.size(); i){for(int j 1; j grid[0].size(); j){dp[i][j] grid[i-1][j-1] min(dp[i-1][j], dp[i][j-1]);}}return dp[grid.size()][grid[0].size()];}
};
10.地下城游戏
link:174. 地下城游戏 - 力扣LeetCode
code1 code2的dp状态表示稍有不同 但是思路相同
code1
class Solution {
public:int calculateMinimumHP(vectorvectorint g) {// 过程最小值min(S1~Sn), 代表的是骑士在这条路上血量最低值假设骑士初始血量0, 也就是所求所需最低初始的健康点数-1的相反数// dp[i][j] : 从i, j)开始到终点的过程最小值// 不给dp开多余空间, dp时注意处理初始化与边界情况即可// 注意dp时反向dpvectorvectorint dp(g.size(), vectorint(g[0].size(), 0));// init dp// dpfor(int i g.size()-1; i 0; i--){for(int j g[0].size()-1; j 0; j--){if(ig.size()-1 jg[0].size()-1) // for内初始化{dp[i][j] g[i][j];continue;}int val1 i1 g.size() ? min(g[i][j], g[i][j] dp[i1][j]) : INT_MIN;// 处理边界情况int val2 (j1 g[0].size())?min(g[i][j], g[i][j] dp[i][j1]):INT_MIN;dp[i][j] max(val1, val2);}printf(\n);}return dp[0][0] 1 ? 1 : -dp[0][0] 1;}
};
code2
class Solution {
public:int calculateMinimumHP(vectorvectorint d) {// dp[i][j]从i, j)出发到终点所需最低初始健康点数// dp[i][j] min(dp[i][j1], dp[i1][j]) - d[i][j]// dp[i][j] max(1, dp[i][j])// dp时init dp即可// 注意dp顺序 倒序dpint m d.size(), n d[0].size();vectorvectorint dp(m1, vectorint(n1, INT_MAX));// init dpdp[m-1][n] dp[m][n-1] 1;// dpfor(int i m-1; i 0; i--){for(int j n - 1; j 0; j--){dp[i][j] min(dp[i1][j], dp[i][j1]) - d[i][j];dp[i][j] max(1, dp[i][j]);}}return dp[0][0];}
}; 三.简单多状态dp问题 dp时如何判断使用哪几种状态
多状态dp中 我们选择的dp状态们必须能覆盖所有情况 这样状态推导时可以保证条件充足状态转移会很轻松
具体示例建议参考6.买卖股票的最佳时机 决策描述/状态描述
决策描述是指用发生了什么决策/事件买入/卖出来标记/描述dp[i]
状态描述是指使用该位置可能所处的状态来描述dp[i]
某个位置的状态描述 不仅可以用此位置的决策/发生事件如买入/卖出来标记状态 还可以使用状态如持有/不持有来标记状态。
特别是当不是每个位置都可能发生决策/事件时我们应采用状态来标记位置这样能保证覆盖所有情况而如果采用决策标记方法则会遗漏不做决策的可能 1.按摩师
link面试题 17.16. 按摩师 - 力扣LeetCode
code1_单一状态dp
class Solution {
public:int massage(vectorint nums) {// dp[i]从num[i]开始(包含nums[i]) 最优预约时长// dp[i] nums[i] max(dp[i2], dp[i3]) //不可能dp[i4]因为此时可以选dp[i2]if(nums.size() 3){if(nums.size()0)return 0;if(nums.size()1)return nums[0];if(nums.size()2)return max(nums[0], nums[1]);}vectorint dp(nums.size(), 0);// init dpint sz nums.size();dp[sz-1] nums[sz-1];dp[sz-2] nums[sz-2];dp[sz-3] nums[sz-1] nums[sz-3];// dpfor(int i sz - 4; i 0; i--){dp[i] nums[i] max(dp[i 2], dp[i 3]);}return max(dp[0], dp[1]);}
};
code2-多状态dp class Solution {
public:int massage(vectorint nums) {// 多状态dp// f[i]:选择nums[i]// g[i]:不选择nums[i]// f[i] g[i-1] nums[i]// g[i] max(f[i-1], g[i-1])if(nums.size()0)return 0;if(nums.size()1) return nums[0];vectorint f(nums.size(), 0);vectorint g(nums.size(), 0);// init dpf[0] nums[0]; g[0] 0;// dpfor(int i 1; i nums.size(); i){f[i] g[i-1] nums[i];g[i] max(g[i-1], f[i-1]);}return max(g[nums.size()-1], f[nums.size()-1]);}
};
2.打家劫舍
link:198. 打家劫舍 - 力扣LeetCode
题意和上道题”按摩师“一样 此题主要为了给打家劫舍II做铺垫
code
class Solution {
public:int rob(vectorint nums){// 不可连续 每房子有偷和不偷两种状态// yes[i] 偷nums[i]// no[i]:不偷nus[i]// yes[i] no[i-1] nums[i]// no[i] max(no[i-1], yes[i-1])if(nums.size()0)return 0;int sz nums.size();vectorint yes(sz);vectorint no(sz);// init dpyes[0] nums[0];no[0] 0;// dpfor(int i 1; i sz; i){yes[i] no[i-1] nums[i];no[i] max(no[i-1], yes[i-1]);}return max(yes[sz-1], no[sz-1]);}
}; 3.打家劫舍II
link213. 打家劫舍 II - 力扣LeetCode
code
class Solution {
public:int rob(vectorint nums) {// 通过分情况讨论是否偷第一家 消除环形影响将问题转化为rob1的线性结构int yes nums.size() 3 ? nums[0] rob1({nums.begin() 2, nums.end()-1}) : nums[0];// 偷第一家 // 就不能偷最后一家int no rob1({nums.begin() 1, nums.end()});// 不偷第一家printf(yes:%d, no:%d\n, yes, no);return max(yes, no);}int rob1(vectorint nums){// 不可连续 每房子有偷和不偷两种状态// yes[i] 偷nums[i]// no[i]:不偷nus[i]// yes[i] no[i-1] nums[i]// no[i] max(no[i-1], yes[i-1])if(nums.size()0)return 0;int sz nums.size();vectorint yes(sz);vectorint no(sz);// init dpyes[0] nums[0];no[0] 0;// dpfor(int i 1; i sz; i){yes[i] no[i-1] nums[i];no[i] max(no[i-1], yes[i-1]);}return max(yes[sz-1], no[sz-1]);}
}; 4.删除并获得点数
link:740. 删除并获得点数 - 力扣LeetCode
code1_多状态dp模拟
class Solution {
public:int deleteAndEarn(vectorint nums) {// 先将nums升序排序 去重// 每个点两种状态删除 不删除// del[i]:删除num[i]情况下 最大点数// sav[i]:不删除num[i]情况下 最大点数// del[i] (nums[i]-nums[i-1]1)?max(sav[i-1], del[i-1]):sav[i-1]// sav[i] nums[i] ((nums[i]-nums[i-1]1)?max(sav[i-1], del[i-1]):sav[i-1])// 预处理numsunordered_mapint, int cnt;for(auto it nums.begin(); it ! nums.end(); it){cnt[*it];}sort(nums.begin(), nums.end());auto it unique(nums.begin(), nums.end());// 也可以set去重nums.erase(it, nums.end());int sz nums.size();if(sz 0)return 0;// check numsfor(int i 0; i sz; i){printf(%d , nums[i]);}printf(\n);// init dpvectorint del(sz);vectorint sav(sz);del[0] nums[0]*cnt[nums[0]];sav[0] 0;for(int i 1; i sz; i){del[i] nums[i]*cnt[nums[i]] ((nums[i]-nums[i-1]1)?max(sav[i-1], del[i-1]):sav[i-1]);sav[i] max(sav[i-1], del[i-1]);}return max(del[sz-1], sav[sz-1]);}
};
code2-转化为打家劫舍
class Solution {
public:int deleteAndEarn(vectorint nums) {// 转化为打家劫舍I#define N (1e4 10)vectorint arr(N, 0);// 预处理arrfor(auto e:nums)arr[e] e;// 相同数消去时可以累加 所以return rob1(arr);}int rob1(vectorint nums){// 不可连续 每房子有偷和不偷两种状态// yes[i] 偷nums[i]// no[i]:不偷nus[i]// yes[i] no[i-1] nums[i]// no[i] max(no[i-1], yes[i-1])if(nums.size()0)return 0;int sz nums.size();vectorint yes(sz);vectorint no(sz);// init dpyes[0] nums[0];no[0] 0;// dpfor(int i 1; i sz; i){yes[i] no[i-1] nums[i];no[i] max(no[i-1], yes[i-1]);}return max(yes[sz-1], no[sz-1]);}
}; 5.粉刷房子
link:LCR 091. 粉刷房子 - 力扣LeetCode
这是一道三状态dp问题
code
class Solution {
public:int minCost(vectorvectorint costs) {// 每个房间三种状态:红 蓝 绿// r[i], b[i], g[i]:第n个房间为r, b, g时需要最小成本// r[i] costs[i][0] min(b[i-1], g[i-1])\// b[i] costs[i][1] min(r[i-1], g[i-1])// g[i] costs[i][2] min(r[i-1], b[i-1])int n costs.size();vectorint r(n), b(n), g(n);// init dpr[0] costs[0][0];b[0] costs[0][1];g[0] costs[0][2];// dpfor(int i 1; i n; i){r[i] costs[i][0] min(b[i-1], g[i-1]);b[i] costs[i][1] min(r[i-1], g[i-1]);g[i] costs[i][2] min(r[i-1], b[i-1]);}return min(min(r[n-1], b[n-1]), g[n-1]);}
}; 6.买股票的最佳时机含冷冻期
link:309. 买卖股票的最佳时机含冷冻期 - 力扣LeetCode
tips:
// 此问题中必须要使用至少三种状态 这样才能包含每种可能状态 方便状态转移中推到当前状态。
// 如果只使用一种状态持有股票或两种状态持有股票和不持有股票都会给状态转移带来不必要麻烦甚至将时间复杂度提升一个等级
// 你可以尝试在本题中只使用一种/两种状态这会使状态转移时非常棘手
更正以上注释掉的部分有误 因为只用两种状态(持有/不持有股票也可以覆盖dp[i]所有可能情况和第七题 依旧是下一题状态表示一样 关于冷冻期调整no[i]刷新策略即可。具体写法见code2-两状态表示
虽然3/2状态都可以正常dp但是一状态只有持有状态就不行了因为不能覆盖dp[i]所有可能状态不可状态转移或者说非常棘手还会将时间复杂度提升一个等级 code1-三状态表示
class Solution {
public:int maxProfit(vectorint prices) {// f[i][0]:第i天后为可买入状态获得的最大利润 / 手里有股票// f[i][1]第i天后为可卖出状态获得的最大利润 / 手里没有股票 没冷冻期// f[i][2]:第i天后是冷冻期状态时获得的最大利润 / 冷冻期vectorvectorint f(prices.size(), vectorint(3, 0));// init dpf[0][0] -prices[0];f[0][1] f[0][2] 0;// dpfor(int i 1; i prices.size(); i){f[i][0] max(f[i-1][0], f[i-1][1] - prices[i]);f[i][1] max(f[i-1][1], f[i-1][2]);// 昨天不能是有股票状态 不然今天就i是冷冻期f[i][2] f[i-1][0] prices[i];}int n prices.size();return max(f[n-1][0], max(f[n-1][1], f[n-1][2]));}
};
code2-两状态表示
class Solution {
public:int maxProfit(vectorint prices) {// have[i]:第i天决策后持有股票// no[i]:第i天不决策后持有股票if(prices.size() 1)return 0;int n prices.size();vectorint have(n1, 0), no(n1, 0);// init dphave[0] -prices[0];no[0] 0;have[1] max(-prices[1], -prices[0]);no[1] max(0, prices[1]-prices[0]);// dpfor(int i 2; i n; i){have[i] max(have[i-1], no[i-2] - prices[i]);no[i] max(have[i-1]prices[i], no[i-1]);}return no[n-1];}
}; 7.买股票的最佳时机含手续费
link:714. 买卖股票的最佳时机含手续费 - 力扣LeetCode
code
class Solution {
public:int maxProfit(vectorint prices, int fee) {// have[i]:第i天决策后有股票// no[i]:第i天决策后没有股票int n prices.size();vector have(n, 0);vector no(n, 0);// init dphave[0] -prices[0];no[0] 0;// dpfor(int i 1; i n; i){have[i] max(have[i-1], no[i-1] - prices[i]);no[i] max(no[i-1], have[i-1] prices[i] - fee);}return no[n-1];}
}; 8.买卖股票的最佳时机III
link:123. 买卖股票的最佳时机 III - 力扣LeetCode
注意本题是的dp状态是二维的
状态机 code
class Solution {
public:int maxProfit(vectorint prices) {// 二维dp状态 完全覆盖所有可能状态// have[i][j]: 第i天后 持有股票且已经完成了j次交易// no[i][j]: 第i天后 不持有股票 且已经完成了j次交易// have[i][j] max(have[i-1][j], no[i-1][j]);// no[i][j] max(no[i-1][j], have[i-1][j-1]);#define MAXN 0x3f3f3f3fint n prices.size();vectorvectorint have(n, vector(3, -MAXN));auto no have;// init dphave[0][0] -prices[0];no[0][0] 0;// dpfor(int i 1; i have.size(); i){for(int j 0; j have[0].size(); j){have[i][j] max(have[i-1][j], no[i-1][j] - prices[i]);no[i][j] max(no[i-1][j], j-10?have[i-1][j-1] prices[i]:-MAXN);}}// return ansint ans 0;for(int cnt 0; cnt have[0].size(); cnt){ans max(ans, no[n-1][cnt]);}return ans;}
}; 9.买卖股票的最佳时机IV
link:188. 买卖股票的最佳时机 IV - 力扣LeetCode
和上题III一样不过2改为k
code
class Solution {
public:int maxProfit(int k, vectorint prices) {// 二维dp状态 完全覆盖所有可能状态// have[i][j]: 第i天后 持有股票且已经完成了j次交易// no[i][j]: 第i天后 不持有股票 且已经完成了j次交易// have[i][j] max(have[i-1][j], no[i-1][j]);// no[i][j] max(no[i-1][j], have[i-1][j-1]);#define MAXN 0x3f3f3f3fint n prices.size();vectorvectorint have(n, vector(k1, -MAXN));auto no have;// init dphave[0][0] -prices[0];no[0][0] 0;// dpfor(int i 1; i have.size(); i){for(int j 0; j have[0].size(); j){have[i][j] max(have[i-1][j], no[i-1][j] - prices[i]);no[i][j] max(no[i-1][j], j-10?have[i-1][j-1] prices[i]:-MAXN);}}// return ansint ans 0;for(int cnt 0; cnt have[0].size(); cnt){ans max(ans, no[n-1][cnt]);}return ans;}
}; 四.子数组系列 1.最大子数组和
link:53. 最大子数组和 - 力扣LeetCode
tips:因为元素可能是负数 则其序列和不具有单调性 不可使用滑动窗口
code
class Solution {
public:int maxSubArray(vectorint nums) {// dp, 子数组系列问题// dp[i]:以i位置结尾的...// dp[i] num[i] max(0, dp[i-1]);vectorint dp(nums.size(), 0);// init dpdp[0] nums[0];// dpfor(int i 1; i nums.size(); i){dp[i] nums[i] max(0, dp[i-1]);}// return ansint ans dp[0];for(int i 1; i dp.size(); i){ans max(ans, dp[i]);}return ans;}
}; 2.环形子数组的最大和
link:
tip:
本题关键是有环 增添了很多边界情况使问题变得棘手。
和打架劫舍II一样 我们可以通过分情况讨论消除环的影响将其变为普通线性结构
两种情况如下 所以我们只需求出线性结构时不成环最大最小子数组和即可 本题中注意nums元素都是负数的情况此时只返回nums中最大元素即可
code class Solution {
public:int maxSubarraySumCircular(vectorint nums) {// 分情况讨论转化为线性结构// f[i]:i结尾线性结构非空子数组最大和// g[i]:i结尾(线性结构)非空子数组最小和// f[i] nums[i] max(0, f[i-1]);// g[i] nums[i] min(0, g[i-1]); // i 0 i n-1int n nums.size();int sum 0;for(int i 0; i nums.size(); i) sumnums[i];vectorint f(n);auto g f;// init dpf[0] g[0] nums[0];// dpfor(int i 1; i f.size(); i){f[i] nums[i] max(0, f[i-1]);g[i] nums[i] min(0, g[i-1]);}// return ans;int ans nums[0];for(int i 1; i f.size(); i){ans max(ans, f[i]);if(g[i] ! sum) ans max(ans, sum - g[i]);// 防止g中出现选取所有元素时间nums都是负数的情况}return ans;}
};
3.乘积最大子数组
link:152. 乘积最大子数组 - 力扣LeetCode
code
class Solution {
public:int maxProduct(vectorint nums) {// f[i]:以i结尾的绝对值最大的正数// g[i]:以i结尾的绝对值最大的负数// 这两个状态保证覆盖寻找 数组中成绩罪的的非空连续子数组 的所需值前最大/最小值int n nums.size();vectorint f(n, 0);auto g f;// init dpf[0] g[0] nums[0];// dpfor(int i 1; i n; i){f[i] max(f[i-1] * nums[i], max(nums[i], g[i-1] * nums[i]));g[i] min(g[i-1] * nums[i], min(nums[i], f[i-1] * nums[i]));}// return ans;int ans nums[0];for(int i 0; i n; i){ans max(ans, f[i]);}return ans;}
}; 4.乘积为正数的最长子数组长度
link:1567. 乘积为正数的最长子数组长度 - 力扣LeetCode
code
class Solution {
public:int getMaxLen(vectorint nums) {// f[i], g[i]:以i结尾的 最长正/负 长度 int n nums.size();vectorint f(n, 0);auto g f;// init dpf[0] nums[0] 0 ? 1 : 0;g[0] nums[0] 0 ? 1 : 0;if(nums[0] 0) g[0] f[0] 0;// dpfor(int i 1; i n; i){if(nums[i] 0){g[i] f[i] 0;continue;}else if(nums[i] 0){f[i] 1 f[i-1];g[i] g[i-1]0 ? 0 : 1 g[i-1];}else // nums[i] 0{g[i] 1 f[i-1];f[i] g[i-1]0 ? 0 : 1 g[i-1];}}// return ansint ans 0;for(int i 0; i n; i){ans max(ans, f[i]);}return ans;}
}; 5.最长湍流子数组
link:978. 最长湍流子数组 - 力扣LeetCode
code
class Solution {
public:int maxTurbulenceSize(vectorint arr) {// dp[i]:以i结尾...if(arr.size() 1) return arr.size();int n arr.size();vectorint dp(n, 0);// init dpdp[0] 1;dp[1] arr[1] ! arr[0] ? 2 : 1;int presub arr[1] - arr[0];// dpfor(int i 2; i n; i){int sub arr[i] - arr[i-1];if(diff(sub, presub)) dp[i] dp[i-1] 1;else dp[i] sub 0 ? 1 : 2;presub sub;}// return ansint ans 0;for(int i 0; i n; i){ans max(ans, dp[i]);}return ans;}bool diff(int a, int b)// 是否异号{if(a 0 || b 0) return false;return (a 0) ^ (b 0);}
}; 6.单词拆分
link:139. 单词拆分 - 力扣LeetCode
code
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {// dp[i]:以s[i]结尾的s的字串是否可被wordDict拼接而成unordered_setstring set(wordDict.begin(), wordDict.end());int n s.size();vectorbool dp(n, false);// init dpdp[0] set.count(s.substr(0, 1));// dpfor(int i 1; i n; i){for(int j i; j 0; j--)// j为最后一个单词的起始位置{if((j-1 0 ? dp[j-1] : true) set.count(s.substr(j, i-j1))){dp[i] true;break;}}}// check dpprintf(dp:\n);for(int i 0; i n; i){printf(dp[%d] : %d\n, i, dp[i]?1:0);}// return ansreturn dp[n-1];}
}; 7.环绕字符串中唯一的子字符串
link:467. 环绕字符串中唯一的子字符串 - 力扣LeetCode
code
class Solution {
public:int findSubstringInWraproundString(string s) {// dp[i]: s[i]结尾的不同非空字串个数中满足条件的不同非空字串// init dpint n s.size();vectorint dp(n, 1);// dpfor(int i 1; i n; i){if(s[i]-s[i-1] 1 || (s[i]a s[i-1]z)) dp[i] 1 dp[i-1];else dp[i] 1;}// 去重int hash[128];memset(hash, 0, sizeof hash);for(int i 0; i dp.size(); i){hash[s[i]] max(hash[s[i]], dp[i]);}// return ansint ans 0;for(int i 0; i 126; i){ans hash[i];}return ans;}
}; 五.子序列问题 子序列 子数组
子数组要求连续子序列不要求连续 但要求相对位置不变 严格递增 不严格递增
严格递增a[i] a[i-1]不严格递增a[i] a[i-1] 1.最长递增子序列
link:300. 最长递增子序列 - 力扣LeetCode
code
class Solution {
public:int lengthOfLIS(vectorint nums) {// 动态规划// dp[i]表示以nums[i]为最后一个元素的最长递增子序列vectorint dp vectorint(nums.size() 5, 1);// init dpdp[0] 1;// dpfor(int i 1; i nums.size(); i){for(int j 0; j i; j){if(nums[j] nums[i]) dp[i] max(dp[i], dp[j] 1);}}int ans dp[0];for(int i 0; i nums.size(); i){ans max(ans, dp[i]);}return ans;}
}; 2.摆动序列
link:376. 摆动序列 - 力扣LeetCode code
class Solution {
public:int wiggleMaxLength(vectorint nums) {// f[i]:以nums[i]结尾的 倒一减倒二大于0的 最长子序列长度// g[i]:以nums[i]结尾的 倒一减倒二小于0的 最长子序列长度if(nums.size() 1) return nums.size();int n nums.size();vectorint f(n, 1);auto g f;// init dpf[1] nums[1] - nums[0] 0 ? 2 : 1;// 上升结尾g[1] nums[1] - nums[0] 0 ? 2 : 1;// dpfor(int i 2; i n; i){for(int j 0; j i; j){int sub nums[i] - nums[j];if(sub 0){f[i] max(g[j] 1, f[i]);}else if(sub 0){g[i] max(f[j] 1, g[i]);}}}// return ans;int ans 0;for(int i 0; i n; i){ans max(ans, max(f[i], g[i]));}return ans;}
}; 3.最长递增子序列的个数
link:673. 最长递增子序列的个数 - 力扣LeetCode
code
class Solution {
public:int findNumberOfLIS(vectorint nums) {// dp[i][0]:nums[i]结尾的 最长递增子序列的 长度// dp[i][1]:nums[i]结尾的 最长递增子序列的 个数if(nums.size() 1) return nums.size();int n nums.size();vectorvectorint dp(n, vectorint(2, 1));// init dp// dpfor(int i 1; i n; i){for(int j 0; j i; j){if(nums[i] nums[j]){if(dp[j][0] 1 dp[i][0]) dp[i][1]dp[j][1];else if(dp[j][0] 1 dp[i][0]){dp[i][0] dp[j][0] 1;dp[i][1] dp[j][1];}}}}// return ans;int maxlen 1;for(int i 0; i dp.size(); i){maxlen max(maxlen, dp[i][0]);}int cnt 0;for(int i 0; i dp.size(); i){if(dp[i][0] maxlen) cnt dp[i][1];}return cnt;}
}; 4.最长数对链
link:646. 最长数对链 - 力扣LeetCode
code
class Solution {
public:int findLongestChain(vectorvectorint pairs) {// 先排序 创造单调性 为使用dp创造条件// dp[i]:排序后 以pairs[i]结尾的 最长数对链的长度sort(pairs.begin(), pairs.end(), [](vectorint vc1, vectorint vc2){return vc1[0] vc2[0];});int n pairs.size();vectorint dp(n, 1);// init dp// dpfor(int i 1; i n; i){for(int j 0; j i; j){if(pairs[j][1] pairs[i][0]){dp[i] max(dp[i], dp[j] 1);}}}// return ans;return dp[n-1];}
};
5.最长定差子序列
link:1218. 最长定差子序列 - 力扣LeetCode
key: 哈希表代替遍历查找arr[i]-d结尾的满足题意的子序列的最大长度 降低时间复杂度
code
class Solution {
public:int longestSubsequence(vectorint arr, int d) {// dp[i]:以arr[i]结尾的 最长等差diff)子序列int n arr.size();vectorint dp(n, 1);unordered_mapint, int hash;// init dp// dpfor(int i 0; i n; i){// 使用hash表避免遍历查找arr[i]-d结尾子序列最大长度dp[i] hash[arr[i]-d] 1;hash[arr[i]] max(hash[arr[i]], dp[i]);}// return ans;int ans 1;for(int i 0; i n; i){ans max(ans, dp[i]);}return ans;}
}; 6.最长的斐波那契子序列长度
link:873. 最长的斐波那契子序列的长度 - 力扣LeetCode
tip: 注意dp时的顺序 先列后行 哈希表避免遍历查询元素下标
code
class Solution {
public:int lenLongestFibSubseq(vectorint arr) {// 二维dp// dp[i][j]:arr[i], arr[j]为最后两元素// 注意初始化顺序先列后行int n arr.size();vectorvectorint dp(n, vectorint(n, 2));unordered_mapint, int map;// 值下标// init dpdp[0][0] 1;for(int i 0 ; i n; i){map[arr[i]] i;}// dpint ans 2;for(int j 2; j dp.size(); j){for(int i 1; i j ; i){int sub arr[j] - arr[i];if(map.count(sub) sub arr[i]) dp[i][j] 1 dp[map[sub]][i];else dp[i][j] 2;ans max(ans, dp[i][j]);}}// return ansprintf(ans %d\n, ans);return ans 3 ? ans : 0;}
};
7.最长等差数列
link:1027. 最长等差数列 - 力扣LeetCode
tips:
和上题 最长斐波那契数列 很类似如果只用dp[i]表示以nums[i]结尾的 最长等差子序列的 长度写不出状态转移方程 因为缺少了dp[j]对应的差值 所以不能判断dp[i]连接在dp[j]后是否为等差数列所以 我们要用二维dp[i][j]表示:最后两项为nums[i],nums[j]的最长子序列长度为什么不用dp[i], len[i]代替dp[i][j]?信息还是不充足 写不出状态转移方程
:注意初始化顺序 只有先i后j才能同时正确地动态初始化hash
code
class Solution {
public:int longestArithSeqLength(vectorint nums) {int n nums.size();vectorvectorint dp(n, vectorint(n, 2));unordered_mapint, int hash;// for(int i 0; i n; i) hash[nums[i]] i;// init dp// dpint ans 2;for(int i 0; i n; i){for(int j i 1; j n; j){int sub nums[j] - nums[i];int target nums[i] - sub;if(hash.count(target) hash[target] i){dp[i][j] dp[hash[target]][i] 1;ans max(ans, dp[i][j]);}}hash[nums[i]] i;// 只有dp顺序为先i后j才能正确初始化hash}// return ansreturn ans;}
}; 8.等差数列划分II-子序列
link:446. 等差数列划分 II - 子序列 - 力扣LeetCode
code
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {// dp[i][j]:以nums[i], nums[j]结尾的等差子序列的 个数using ll long long int;int n nums.size();vectorvectorint dp(n, vectorint(n, 0));unordered_mapll, vectorint hash;for(int i 0; i n; i) hash[nums[i]].push_back(i);// init dpint ans 0;for(int j 2; j n; j){for(int i 1; i j; i){ll a 2 * ll(nums[i]) - nums[j];for(int idx:hash[a]){if(idx i) dp[i][j] dp[idx][i] 1;}ans dp[i][j];}}return ans;}
}; 六.回文串问题 1.回文子串
link:647. 回文子串 - 力扣LeetCode code
class Solution {
public:int countSubstrings(string s) {// dp[i][j]:s[i:j]是否为回文串int n s.size();vectorvectorint dp(n, vectorint(n, 0));// dp// 由下向上dpfor(int i n - 1; i 0; i--){for(int j i; j n; j){if(s[i] ! s[j]){dp[i][j] false;continue;}if(i 1 j - 1){dp[i][j] dp[i1][j-1];}else{dp[i][j] true;}}}// return ans;int ans 0;for(int i 0; i n; i){for(int j i; j n; j){ans dp[i][j];}}return ans;}
}; 2.最长回文字串
link:5. 最长回文子串 - 力扣LeetCode
code
class Solution {
public:string longestPalindrome(string s) {// dp[i][j]:s[i][j]是否为回文字串int maxlen 0;int bgn 0;int n s.size();vectorvectorint dp(n, vectorint(n, 0));// dpfor(int i n; i 0; i--){for(int j i; j n; j){if(s[i] s[j]){dp[i][j] i 1 j - 1 ? dp[i1][j-1] : true;}else dp[i][j] false;int len j - i 1;if(dp[i][j] len maxlen){maxlen len;bgn i;}}}printf(bgn %d, maxlen %d\n, bgn, maxlen);return s.substr(bgn, maxlen);}
}; 3.分割回文串
link:1745. 分割回文串 IV - 力扣LeetCode
code
class Solution {
public:bool checkPartitioning(string s) {// dp[i][j]:s[i:j]是否为回文串int n s.size();vectorvectorbool dp(n, vectorbool(n, false));// dpfor(int i n - 1; i 0; i--){for(int j i; j n; j){if(s[i] s[j]){dp[i][j] i 1 j - 1 ? dp[i1][j-1] : true;}}}// return ans// 判断s[0:i], s[i1:j], s[j1:]是否为回文for(int i 0; i n - 2; i){for(int j i 1; j n - 1; j){if(dp[0][i] dp[i1][j] dp[j1][n-1]){return true;}} }return false;}
}; 5.分割回文串II
link:132. 分割回文串 II - 力扣LeetCode
code
class Solution {
public:int minCut(string s) {#define INF 0x3f3f3f3fint n s.size();vectorvectorbool huiwen(n, vectorbool(n, false));// dpfor(int i n - 1; i 0; i--){for(int j i; j n; j){if(s[i] s[j]){huiwen[i][j] i 1 j - 1 ? huiwen[i1][j-1] : true;}}}// dpvectorint dp(n, INF);// dp[i]:s[:i]最少分割数for(int i 0; i n; i){if(huiwen[0][i]){dp[i] 0;continue;}for(int j 1; j i; j)// dp[j:i]是最后一个回文串{if(huiwen[j][i]){dp[i] min(dp[i], dp[j-1] 1);}}}return dp[n-1];}
}; 七.两个数组的dp问题 1.最长公共子序列
这是非常非常经典的一道两数组dp问题 很有借鉴/学习意义。
link:1143. 最长公共子序列 - 力扣LeetCode
code
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {// dp[i][j]:text1[:i], text2[:j]最长公共子序列int n text1.size();int m text2.size();vectorvectorint dp(n 1, vectorint(m 1, 0));// 空串方便初始化text1 text1;text2 text2;// 保证坐标对应// dpfor(int i 1; i n; i){for(int j 1; j m; j){if(text1[i] text2[j])dp[i][j] dp[i-1][j-1] 1;elsedp[i][j] max(dp[i-1][j], dp[i][j-1]);}}return dp[n][m];}
};
tips:
字符串/子序列中 空串是有意义的而且加上空串也会方便初始化防止越界 2.不相交的线
其实就是最长公共子序列
link:1035. 不相交的线 - 力扣LeetCode
code
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {// 就是求最长公共子序列// dp[i][j]:nums1[:i], nums2[:j]最大连线数int n nums1.size();int m nums2.size();vectorvectorint dp(n 1, vectorint(m 1, 0));nums1.insert(nums1.begin(), -1);nums2.insert(nums2.begin(), -2);// 保证下标对应// dpfor(int i 1; i n; i){for(int j 1; j m; j){if(nums1[i] nums2[j])dp[i][j] dp[i-1][j-1] 1;elsedp[i][j] max(dp[i-1][j], dp[i][j-1]);}}return dp[n][m];}
}; 3.不同的子序列
link:115. 不同的子序列 - 力扣LeetCode
key: 空串往往是有意义的一定要考虑空串情况 init dp时dp[i][0] 1 代表s[:i]中有一个
code
class Solution {
public:int numDistinct(string s, string t) {// dp[i][j]:在s[:i]中 t[j]出现的个数#define MOD (int(1e9 7))int n s.size();int m t.size();vectorvectorint dp(n 1, vectorint(m 1, 0));s s;t t;// 下标对应// init dp 注意 空串也是有意义的 dp[i][0] 1, 代表s[:i]中有一个 dp[0][0] 1;for(int i 1; i n; i) dp[i][0] 1;// dpfor(int i 1; i n; i){for(int j 1; j m; j){ // 求s[:i]中 多少次t[:j]if(s[i] t[j]) dp[i][j] (dp[i-1][j-1] dp[i-1][j]) % MOD;// 以s[:i]结尾的t[:j]个数 s[:i-1]内t[:j]个数elsedp[i][j] dp[i-1][j] % MOD;// s[:i-1]内t[:j]个数}}return dp[n][m];}
}; 4.通配符匹配
link:44. 通配符匹配 - 力扣LeetCode
tips: 本题关键p[j]*时状态转移方程 本题有两种方法推导出上述答案(dp[i][j] dp[i-1][j] || dp[i][j-1]):数学法和实际分析法 code
class Solution {
public:bool isMatch(string s, string p) {// dp[i][j]:s[:i]是否可以匹配p[:j]// key:p[j]*时状态转移方程int n s.size();int m p.size();vectorvectorint dp(n 1, vectorint(m 1, false));s s;p p;// init dpdp[0][0] true;// 空串可以匹配空串for(int i 1; i m; i) // *可匹配空串{if(p[i]*){dp[0][i] true;}else break;}// dp// for(int i 1; i n; i)for(int j 1; j m; j){// for(int j 1; j m; j)for(int i 1; i n; i){if(p[j] *) dp[i][j] dp[i][j-1] || dp[i-1][j];else if(p[j] s[i] || p[j] ?)dp[i][j] dp[i-1][j-1];else dp[i][j] false; p[j]不是*且p[j] ! s[i]:一定不能匹配}}return dp[n][m];}
}; 5.正则表达式匹配
link:10. 正则表达式匹配 - 力扣LeetCode
和上题差不多 只是*匹配规则有变化导致p[j]‘*’时状态转移方程有些许小变化但两题思路/做法相同
key: dp init p[j] *时状态转移方程 code
class Solution {
public:bool isMatch(string s, string p) {// dp[i][j]: p[:j]能否匹配s[:i]int n s.size();int m p.size();vectorvectorbool dp(n 1, vectorbool(m 1, false));s s;p p;// 下标对齐 考虑空串// init dpdp[0][0] true;// 空串可以匹配空串// p .*a*b*?*..........时 可匹配s(空)for(int j 2; j m; j 2) {if(p[j] *) dp[0][j] true;else break;}// dpfor(int j 1; j m; j){for(int i 1; i n; i){if (p[j] *) dp[i][j] dp[i][j-2] || ((p[j-1] . || p[j-1] s[i]) dp[i-1][j]);// key,分两种情况*匹配0个前字符(dp[i][j-2])/// *匹配1至多个前字符((p[j-1] . || p[j-1] s[i]) dp[i-1][j])else if(p[j] s[i] || p[j] .) dp[i][j] dp[i-1][j-1];else dp[i][j] false;}}return dp[n][m];}
}; 6.交错字符串
link:97. 交错字符串 - 力扣LeetCode
本题比较容易退出状态表示和状态转移方程
code
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {// dp[i][j]:s1[:i], s2[:j]是否可以交错形成s3[:ij]if(s1.size() s2.size() ! s3.size()) return false;int n s1.size();int m s2.size();s1 s1;s2 s2;s3 s3;vectorvectorbool dp(n 1, vector(m 1, false));// init dpdp[0][0] true;for(int i 1; i n; i) {if(s1[i] s3[i]) dp[i][0] true;else break;}for(int j 1; j m; j) {if(s2[j] s3[j]) dp[0][j] true;else break;}// dpfor(int i 1; i n; i){for(int j 1; j m; j){bool ret1 s1[i]s3[ij] dp[i-1][j];bool ret2 s2[j]s3[ij] dp[i][j-1];dp[i][j] ret1 || ret2;}}return dp[n][m];}
}; 7.两个字符串的最小ASCII删除和
link:712. 两个字符串的最小ASCII删除和 - 力扣LeetCode
key: 正难则反 将求最小删除ASCII值转化为求公共子序列最大ASCII值 状态转移时 按照公共子序列最后一个字符是否有s1[i]和s2[j]两个字符分情况即可 code
class Solution {
public:int minimumDeleteSum(string s1, string s2) {// 正难则反 求删除字符ASCII最小和 就是求公共子序列的最大ASCII和// dp[i][j]:s1[:i], s2[:j]公共子序列的最大ASCII// 状态转移时 根据公共子序列是否包含s1[i],s2[j]字符,分情况即可// 或者说 公共子序列最后一个字符是否是s1[i],s2[j]int n s1.size(); int m s2.size();s1 s1;s2 s2;vectorvectorint dp(n 1, vectorint(m 1, 0));// init dp// 空串情况都是0 创建dp时已经初始化// dpfor(int i 1; i n; i){for(int j 1; j m; j){if (s1[i] s2[j]) dp[i][j] dp[i-1][j-1] s1[i];// s1[i],s2[j]都能用到else dp[i][j] max(dp[i-1][j], dp[i][j-1]);// s1[i],s2[j]至少一个用不到}}// return ans;int sum1 0, sum2 0;for(int i 1; i n; i) sum1 s1[i];for(int j 1; j m; j) sum2 s2[j];return sum1 sum2 - 2 * dp[n][m];}
}; 8.最长重复子数组
link:718. 最长重复子数组 - 力扣LeetCode
tips: 这是一道比较简单的双数组dp问题 注意求子数组时的dp状态表示dp[i][j]一定表示的是以nums1[i], nums2[j]为结尾的子数组。 这点不同于子序列因为子序列不要求连续所以子序序列问题的dp状态表示不要求也不能要求指定结尾 code
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {// 由于本题是求子数组长度子数组要求连续所以dp[i][j]一定要保证是结尾状态 不能像子序列一样的区间状态// dp[i][j]:以nums1[i], nums2[j]结尾的最长子数组的长度int n nums1.size();int m nums2.size();nums1.insert(nums1.begin(), -1);nums2.insert(nums2.begin(), -2);vectorvectorint dp(n 1, vectorint(m 1, 0));// dpint ans 0;for(int i 1; i n; i){for(int j 1; j m; j){if(nums1[i] nums2[j]){dp[i][j] dp[i-1][j-1] 1;}ans max(ans, dp[i][j]);}}return ans;}
}; 01背包问题
01背包问题是所有背包问题的基础
背包问题有很多条件/性质
01背包/完全背包不必装满 / 必须塞满....
背包问题的条件很多这些条件排列组合使得背包问题有很多种 1.【模板】01背包
link:【模板】01背包_牛客题霸_牛客网
code
FULL中没有使用滚动数组优化
IsFULL中使用了滚动数组优化
#include iostream
#include vector
using namespace std;int n, V;
vectorint v, w;int NotFull();
int Full();int main() {cinnV;v vectorint(n 1);// 注意下标对应w v;for(int i 1; i n; i){cinv[i]w[i];}// 注意n个物体中每个物体最多只能选择一次01背包问题int ans1 NotFull();int ans2 Full();coutans1endl;coutans2endl;
}int NotFull()
{// dp[i][j]:前i个物品背包容量j最多能装多大价值的物品vectorint dp vectorint(V 1, 0); // 一行滚动数组// init dp// 已经初始化dp第一行第一列默认为0// dpfor(int i 1; i n; i){for(int j V; j 1; j--)// 反向遍历{// 装下第i物品int val1 j-v[i] 0 ? dp[j-v[i]] w[i] : 0;// 不装i物品int val2 dp[j];dp[j] max(val1, val2);}}return dp[V];
}int Full()
{// dp[i][j]:前i个物品背包容量j恰好装满能装多大价值的物品vectorvectorint dp(n 1, vectorint(V 1, 0));// init dpfor(int j 1; j V; j) dp[0][j] -1;// -1表示dp[i][j]不可能恰好装满// dpfor(int i 1; i n; i){for(int j 1; j V; j){int val1, val2;// 装下第i物品if(j - v[i] 0){val1 dp[i-1][j-v[i]] ! -1 ? dp[i-1][j-v[i]] w[i] : -1;}else val1 -1;// 不装i物品val2 dp[i-1][j];dp[i][j] max(val1, val2);}}return dp[n][V] -1 ? 0 : dp[n][V];
}
// 64 位输出请用 printf(%lld)
滚动数组优化空间复杂度
可以仅使用一行空间存储滚动数组但此时注意初始化顺序从右向左防止覆盖所需值
不必强行解释上述优化后的dp意义。知道如何从源代码优化即可不必深究优化后意义
滚动数组优化步骤
非常简单 记住一下两步即可
删除dp的所有行坐标列坐标从右向左遍历
