济南网站开发公司,wordpress twenty,asp网站链接access,心理咨询网站目录
一、打家劫舍
二、打家劫舍 II
三、删除并获得点数
四、粉刷房子
五、买卖股票的最佳时机含冷冻期
六、买卖股票的最佳时机含手续费
七、买卖股票的最佳时机III
八、买卖股票的最佳时机IV 一、打家劫舍
打家劫舍 第一步#xff1a;确定状态表示
当我们每次…目录
一、打家劫舍
二、打家劫舍 II
三、删除并获得点数
四、粉刷房子
五、买卖股票的最佳时机含冷冻期
六、买卖股票的最佳时机含手续费
七、买卖股票的最佳时机III
八、买卖股票的最佳时机IV 一、打家劫舍
打家劫舍 第一步确定状态表示
当我们每次偷到第i间房子时我们存在两种状态即可以选择偷或者不偷该房子的金额。所以我们需要有两张dp表。
f[ i ] 表示偷到第 i 间房子时小偷选择偷第 i 间房子的金额时偷窃到的总金额最大。g[ i ]表示偷到第 i 间房子时小偷选择不偷第 i 间房子的金额时偷窃到的总金额最大。 第二步推出状态转移方程 第三步初始化dp表
我们在使用状态转移方程时会用到 i-1位置的值那么如果 i 为0的话就会有越界访问的问题所以我们需要初始化f[0] nums[0]g[i] 0。
填表顺序因为在填写 i 位置的值时我们要用到 i-1位置的值所以需要从左往右依次填写。
最后的返回值我们要返回光顾完所有房子后所能偷到的最大金额所以需要返回f[n-1] 和 g[i-1]两者的最大值。
解题代码
class Solution
{
public:int rob(vectorint nums) {int n nums.size();vectorint f(n);vectorint g(n);f[0] nums[0];for(int i 1; i n; i){f[i] g[i-1] nums[i];g[i] max(f[i-1], g[i-1]);}return max(f[n-1], g[n-1]);}
}; 二、打家劫舍 II
打家劫舍II 打家劫舍II和打家劫舍问题唯一不同的是这道题的房子是围成一个圈的。我们可以将它转换成打家劫舍问题去处理。 其他方法就和打家劫舍问题一样了。
返回值就是上面两种情况的最大值。
解题代码
class Solution
{
public:int rob(vectorint nums) {int n nums.size();return max(nums[0] rob1(nums, 2, n-2), rob1(nums, 1, n-1));}int rob1(vectorint nums, int left, int right){int n nums.size();if(left right)return 0;vectorint f(n);vectorint g(n);f[left] nums[left]; // 区间的起始位置是leftfor(int i left; i right; i){f[i] g[i-1] nums[i];g[i] max(g[i-1], f[i-1]);}return max(g[right], f[right]); // 区间的最右是right}
}; 三、删除并获得点数
删除并获得点数 预处理我们需要注意题目说明中的这一句选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除所有等于 nums[i] - 1 和 nums[i] 1 的元素。
也就是说你在拿到nums[i]的点数后就不能选择它前一个和后一个元素了。比如nums[i]为5拿到5这个点数后你就不能再拿3和4了。这个要求是不是又和打家劫舍很像了。所以我们最终还是将这个问题转换成了打家劫舍问题。
比如对于示例2 解题代码
class Solution
{
public:int deleteAndEarn(vectorint nums) {int arr[10001] {0};for(auto x : nums)arr[x] x;vectorint f(10001);vectorint g(10001);f[0] arr[0];for(int i 1; i 10001; i){f[i] g[i-1] arr[i];g[i] max(g[i-1], f[i-1]);}return max(g[10000], f[10000]);}
}; 四、粉刷房子
粉刷房子 第一步确定状态表示
红0蓝1绿2。
dp[i][j]表示刷到第i个房子时将其涂成第j种颜色时的最小花费。
第二步推出状态转移方程 第三步初始化dp表
在使用dp表时要使用i-1所以 i 0时就会发生越界访问的问题。所以初始化
dp[0][0] costs[0][0]dp[0][1] costs[0][1]dp[0][2] costs[0][2]。
填表顺序从上向下从左到右
最后的返回值是最后一行的最大值。
解题代码
class Solution
{
public:int minCost(vectorvectorint costs) {int m costs.size(), n costs[0].size();// 红0蓝1绿2// dp[i][j]:表示刷到第i个房子时将其涂成第j种颜色时的最小花费vectorvectorint dp(m, vectorint(3));dp[0][0] costs[0][0], dp[0][1] costs[0][1], dp[0][2] costs[0][2];for(int i 1; i m; i){dp[i][0] min(dp[i-1][1], dp[i-1][2]) costs[i][0];dp[i][1] min(dp[i-1][0], dp[i-1][2]) costs[i][1];dp[i][2] min(dp[i-1][0], dp[i-1][1]) costs[i][2];}return min(dp[m-1][0], min(dp[m-1][1], dp[m-1][2]));}
}; 五、买卖股票的最佳时机含冷冻期
买卖股票的最佳时机含冷冻期 第一步确定状态表示
根据题意和示例大的状态表示就是在第i天结束后所获得的最大利润而对于第i天来说我们又有三种可能的状态卖出买入冷冻期。
卖出状态0买入状态1冷冻期2
所以说dp[i][j]表示第 i 天结束后处于第 j 种状态时所获的最大利润。
dp[i][0] 表示 第 i 天结束之后处于卖出状态此时的最大利润。
dp[i][1] 表示 第 i 天结束之后处于买入状态此时的最大利润。
dp[i][2] 表示 第 i 天结束之后处于冷冻期状态此时的最大利润。
第二步推出状态转移方程 对于上面的核心图我们对卖出状态进行举例解释一下
如果在第 i 天结束后处于卖出状态需要看 i - 1 天是什么状态然后怎么做能够满足第 i 天结束处于卖出状态。
如果第 i - 1 天结束处于卖出状态那第 i 天什么也不干依旧处于卖出状态。
如果第 i - 1 天结束处于冷冻期也就是说第 i 天不能进行任何操作无法购买股票当第 i 天结束后就会结束冷冻期进入卖出状态。
第三步初始化dp表dp[0][1] -prices[0]。
从左往右从上向下依次填表最后返回最后一天的三种状态中的最大值。
解题代码
class Solution
{
public:int maxProfit(vectorint prices) {int m prices.size();vectorvectorint dp(m, vectorint(3));dp[0][1] -prices[0];// 卖0买1冷冻2for(int i 1; i m; i){dp[i][0] max(dp[i-1][0], dp[i-1][2]);dp[i][1] max(dp[i-1][1], dp[i-1][0]-prices[i]);dp[i][2] dp[i-1][1]prices[i];}return max(max(dp[m-1][0], dp[m-1][1]), dp[m-1][2]);}
}; 六、买卖股票的最佳时机含手续费
买卖股票的最佳时机含手续费 第一步确定状态表示
根据题意每一天都可能存在两种状态买入状态和卖出状态。
所以f[i]表示第 i 天结束后处于买入状态时所获的最大利润。g[i]表示第 i 天结束后处于卖出状态时所获的最大利润。
需要注意的是每次卖出股票需要支付手续费。
第二步推出状态转移方程 第三步初始化dp表f[0] -prices[0]。
填表顺序为从左往右依次填写g[i]和f[i]一起填写。最后的返回值是f[m-1]和f[m-1]中的最大值。
解题代码
class Solution
{
public:int maxProfit(vectorint prices, int fee) {int m prices.size();vectorint f(m);vectorint g(m);f[0] -prices[0];for(int i 1; i m; i){f[i] max(f[i-1], g[i-1] - prices[i]);g[i] max(g[i-1], f[i-1] prices[i] - fee);}return max(f[m-1], g[m-1]);}
}; 七、买卖股票的最佳时机III
买卖股票的最佳时机III 第一步确定状态表示
首先仍然是 dp[i] 表示第 i 天结束后所获得的最大利润。每一天有两种状态卖出和买入状态。
而这道题和之前的题目不同的就是它有交易次数的限制只能够完成两笔交易。所以对于每一天来说在卖出和买入状态之下还有一种状态那就是一直到第 i 天的交易次数。
所以dp[i][j] 表示第 i 天结束后完成了 j 次交易后所获得的最大利润。0表示完成了0次交易1表示完成了1次交易2表示完成了2次交易。
f[i][j] 表示第 i 天结束后处于买入状态时完成了 j 次交易后所获得的最大利润。
g[i][j] 表示第 i 天结束后处于卖出状态时完成了 j 次交易后所获得的最大利润。
第二步推出状态转移方程 第三步初始化dp表 填表顺序为从左往右从上往下依次填写g[i]和f[i]一起填写。
解题代码
class Solution
{const int n -0x3f3f3f3f;
public:int maxProfit(vectorint prices) {int m prices.size();vectorvectorint f(m, vectorint(3, n)); // 买入vectorvectorint g(m, vectorint(3, n)); // 卖出f[0][0] -prices[0], g[0][0] 0;for(int i 1; i m; 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 i 0; i 3; i){if(g[m-1][i] ret)ret g[m-1][i];}return ret;}
}; 八、买卖股票的最佳时机IV
买卖股票的最佳时机IV 这一道题的思路和买卖股票的最佳时机III一模一样只是把最多交易次数限定成了一个未知数。我们所有的解题方法都与他相同。
解题代码
class Solution
{const int n -0x3f3f3f3f;
public:int maxProfit(int k, vectorint prices) {int m prices.size();vectorvectorint f(m, vectorint(k1, n)); // 买入vectorvectorint g(m, vectorint(k1, n)); // 卖出f[0][0] -prices[0], g[0][0] 0;for(int i 1; i m; i){for(int j 0; j k; 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 i 0; i k; i){if(g[m-1][i] ret)ret g[m-1][i];}return ret;}
};
