如何更快的学习.net网站开发,wordpress数据库容量,大型户外广告设计公司,摄影工作室网站建设模板多状态dp就是dp[i]可能不只有一种状态 我们要分析这些状态之间的含义关系 当多种状态可以互相转换的时候最好画一张图 分析关系 #xff08;买股票问题很典型的状态之间互相转换#xff09; 分析清楚之后可以得出状态转移方程 一、按摩师 面试题 17.16. 按摩师 - 力扣 if(n 0) return 0; else if(n 1) return nums[0]; else if(n 2) return max(nums[0], nums[1]); else { vectorint dp(n, 0); dp[0] nums[0]; dp[1] max(dp[0], nums[1]); for(int i 2; i n; i) { dp[i] max(dp[i-1], dp[i-2] nums[i]); } return dp[n-1]; } return 0; } }; // dp[i] 表示0~i位置之间最长总时长 // dp[i] 可以选或者不选 所以dp[i] max(dp[i-1], dp[i-2]nums[i]);二、打家劫舍II 213. 打家劫舍 II - 力扣LeetCodeclass Solution { public: int rob(vectorint nums) { int n nums.size(); if(n 0 ) return 0; else if(n 1) return nums[0]; // 先算出第一种情况的值 int ans1 nums[0]; vectorint f(n, 0); // 选nums[i]的最大值 vectorint g(n, 0); // 不选nums[i]的最大值 for(int i 2; i n-1; i) { f[i] nums[i] g[i-1]; g[i] max(f[i-1], g[i-1]); // 不选nums[i]前面可能也不选 所以要从前面选或者不选之间选择最大值 } ans1 max(f[n-2], g[n-2]); // 第二种情况 int ans2 0; for(int i 1; i n; i) { f[i] nums[i] g[i-1]; g[i] max(f[i-1], g[i-1]); } ans2 max(f[n-1], g[n-1]); return max(ans1, ans2); } }; // 分类讨论 选择nums[0]则第二个和最后一个位置不能选 那么此时加上 [2, n-2]之间打家劫舍I类型的最大值 // 不选择nums[0] 则加上[1, n-1]之间打家劫舍I的最大值三、740. 删除并获得点数 - 力扣LeetCodeclass Solution { public: int deleteAndEarn(vectorint nums) { int n nums.size(); // 选出最大值开辟数组 进行预处理 int maxn 0; for(int i 0; i n; i) { maxn max(maxn, nums[i]); } vectorint arr(maxn1, 0); for(int i 0; i n; i) { arr[nums[i]] nums[i]; } auto f arr, g arr; f[0] arr[0]; g[0] 0; for(int i 1; i maxn1; i) { f[i] arr[i] g[i-1]; g[i] max(f[i-1], g[i-1]); } return max(f[maxn], g[maxn]); } }; // 每个位置选或者不选 这其实也是打家劫舍问题 但是呢打家劫舍里面下标是连续的所以很好填dp表 // 这里的数字可能出现间断 所以要先预处理一下 将数据映射到一个数组里面 下标位置代表这个和这个下标相同数据的总和 那么就可以使用打家劫舍解题了四、LCR 091. 粉刷房子 - 力扣LeetCodeclass Solution { public: int minCost(vectorvectorint costs) { int n costs.size(); vectorvectorint dp(n, vectorint(3, 0)); dp[0][0] costs[0][0]; dp[0][1] costs[0][1]; dp[0][2] costs[0][2]; for(int i 1; i n; i) { // 选择红色 那么前一个选蓝或者绿 从这两个中选较小值 // 其他情况类似 dp[i][0] costs[i][0] min(dp[i-1][1], dp[i-1][2]); dp[i][1] costs[i][1] min(dp[i-1][0], dp[i-1][2]); dp[i][2] costs[i][2] min(dp[i-1][0], dp[i-1][1]); } return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2])); } }; // 按照经验来说 这个也是线性dp问题 那么可以以某个位置为结尾建立dp表 // dp[i]表示在i位置选取一个颜色之后最小花费 // i位置可以选三种颜色 因此需要用dp[i][0/1/2]分别表示i位置选红、蓝、绿之后的最小花费 // 最后返回dp[n-1][0/1/2]之间的最小值五、309. 买卖股票的最佳时机含冷冻期 - 力扣LeetCodeclass Solution { public: int maxProfit(vectorint prices) { int n prices.size(); vectorvectorint dp vector(n, vectorint(3)); // 初始化 dp[0][0] -prices[0]; dp[0][1] 0; dp[0][2] 0; for(int i 1; i n; i) { dp[i][0] max(dp[i-1][0], dp[i-1][2]-prices[i]); dp[i][1] dp[i-1][0] prices[i]; dp[i][2] max(dp[i-1][2], dp[i-1][1]); } return max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2])); } }; // 思路 // 根据经验设置一个状态表dp[i] 表示这一天结束之后获取到的最大利益 // 不过每一天可能含义不同 // 因为每一天可以进行的操作有买入 卖出 或者什么都不做 // 而这些操作做完之后对应着三种状态 买入 冷冻期 可交易 // 那么应该这样设状态表 // dp[i][0]表示第i天结束之后 处于‘买入’状态 可以获取的最大利益 // dp[i][1]表示第i天结束之后 处于‘冷冻期’状态 可以获取的最大利益 // dp[i][2]表示第i天结束之后 处于‘可交易’状态 可以获取的最大利益 // 这三个状态之间存在转移关系 因此可以根据前一天也就是dp[i-1][0/1/2]来退出dp[i][0/1/2] // 推导过程 // 若是第i天结束之后 处于买入状态 前一天结束之后可能是买入状态吗 可以 i天的时候什么都不做即可前一天结束后可以是冷冻期吗 不行 前一天结束后状态为冷冻期 那么第i天的时候什么都不能做 前一天结束的时候可以是可交易吗 可以 第i天的时候买入股票即可 // 若是第i天结束之后 处于冷冻期状态 前一天结束可以是冷冻期吗 不可以 因为第i天已经冷冻了 可以是买入吗 可以 第i天的时候 卖出可以是可交易吗 不行 因为第i天的时候不可能卖票 // 若是第i天结束之后 处于可交易状态 前一天结束之后可以是 可交易吗 可以 什么都不做买入呢 不行 冷冻期呢 可以 第i天被冷冻 第i天结束之后 恢复正常 可以交易 // 状态转移方程 // dp[i][0] max(dp[i-1][0], dp[i-1][2]-prices[i]); // dp[i][1] dp[i-1][0] prices[i]; // dp[i][2] max(dp[i-1][2], dp[i-1][1]);六、714. 买卖股票的最佳时机含手续费 - 力扣LeetCodeclass Solution { public: int maxProfit(vectorint prices, int fee) { int n prices.size(); vectorvectorint dp vector(n, vectorint(2)); 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]-fee); } return max(dp[n-1][0], dp[n-1][1]); } }; // dp[n][2]: // dp[i][0]表示第i天结束 处于状态‘买入’ 能获得的最大利益 // dp[i][1]表示第i天结束 处于状态‘可交易’ 能获得的最大利益 // 这两个状态可以互相转移 画图得出关系 推导出状态转移方程七、123. 买卖股票的最佳时机 III - 力扣LeetCodeclass Solution { public: const int INF 0x3f3f3f3f; int maxProfit(vectorint prices) { int n prices.size(); vectorvectorint f(n, vectorint(3)), g(n, vectorint(3)); f[0][0] -prices[0]; f[0][1] -INF; f[0][2] -INF; g[0][0] 0; g[0][1] -INF; g[0][2] -INF; for (int i 1; i n; i) { for (int j 0; j 3; j) { f[i][j] max(f[i-1][j], g[i-1][j] - prices[i]); g[i][j] g[i-1][j]; if(j-1 0) g[i][j] max(g[i-1][j], f[i-1][j-1] prices[i]); } } int ret 0; for (int j 0; j 3; j) { ret max(ret, g[n-1][j]); } return ret; } }; // 状态分析 // 每天结束之后可以处于买入或者卖出的状态 分别用f[i] g[i]表示每天结束之后处于买入或者卖出状态的最大利润 // 但是存在交易次数限制 因此f和g要是二维数组 f[i][j] g[i][j] 表示某一天结束之后处于买入或者卖出状态且完成j笔交易的最大利润 // 根据经验 某一天的利润可以由前一天推来 // 状态转移方程 //第i天结束之后处于买入 前一天到今天结束状态可以不变 那么就是啥也不做 即f[i][j] f[i-1][j] 状态变为卖出 就是前一天的利润加上prices[i] 只有卖出的时候表示一次交易完成 今天结束完成j笔交易 那么前一天就是j-1次 即f[i][j] g[i-1][j-1] prices[i] 第i天结束之后状态为卖出 前一天到今天结束可以不变就是啥也不做 即g[i][j] g[i-1][j] 变为买入 就是前一天最大利润减去prices[i] 即g[i][j] f[i-1][j-1] - prices[i] // 总结就是 f[i][j] max(f[i-1][j], g[i-1][j] - prices[i]) g[i][j] max(g[i-1][j], f[i-1][j-1] prices[i]) // 初始化 //首先开两个n行 3列的二维数组 因为最多完成2笔交易 那么可以是0、1、2笔交易 // 两个数组都要初始化第一行 因为使用到了i-1 f[0][0] -prices[0] g[0][0] 0 因为存在交易次数限制 所以每次交易的机会十分宝贵 尽可能要赚更多的利润 所以多次当天买当天卖不行 第一行表示第一天 那么1、2两列的位置表示第1天结束完成了多笔交易 这个位置不能被纳入结果利润选择的范围 因此初始化为-0x3f3f3f3f(INT_MIN的一半 避免减去之后越界) // g的使用有一个j-1 当j0的时候 表示完成-1笔交易 明显不合逻辑 因此为了方便代码编写 改写一下状态转移方程 f不变 g[i][j]g[i-1][j], 之后if(j-1 0) 才g[i][j] max(g[i-1][j], f[i-1][j-1] prices[i]) 这样就不会越界了 // 返回值 //肯定最后要卖出 因此从g表的最后一行所有值中选最大值 因为交易次数有很多种八、188. 买卖股票的最佳时机 IV - 力扣LeetCodeclass Solution { public: const int INF 0x3f3f3f3f; int maxProfit(int k, vectorint prices) { int n prices.size(); vectorvectorint f(n, vectorint(k1, -INF)), g(n, vectorint(k1, -INF)); f[0][0] -prices[0]; g[0][0] 0; for (int i 1; i n; i) { for (int j 0; j k1; j) { f[i][j] max(f[i-1][j], g[i-1][j] - prices[i]); g[i][j] g[i-1][j]; if(j-1 0) g[i][j] max(g[i-1][j], f[i-1][j-1] prices[i]); } } int ret 0; for (int j 0; j k1; j) { ret max(ret, g[n-1][j]); } return ret; } }; // 思路和买股票的最佳时机III一样 只是交易次数变为不定的了