个人购物网站搭建,网站特效怎么做的,宜昌优化网站建设,学校二级网站建设简单多状态 1. 按摩师#xff08;easy#xff09;2. 打家劫舍II #xff08;medium#xff09;3. 删除并获得点数#xff08;medium#xff09;4. 买卖股票的最佳时机含冷冻期#xff08;medium#xff09;5. 买卖股票的最佳时机III#xff08;hard#xff09; 1. 按… 简单多状态 1. 按摩师easy2. 打家劫舍II medium3. 删除并获得点数medium4. 买卖股票的最佳时机含冷冻期medium5. 买卖股票的最佳时机IIIhard 1. 按摩师easy
1.题目链接按摩师 2.题目描述一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。 示例 1 输入 [1,2,3,1] 输出 4 解释 选择 1 号预约和 3 号预约总时长 1 3 4。 示例 2 输入 [2,7,9,3,1] 输出 12 解释 选择 1 号预约、 3 号预约和 5 号预约总时长 2 9 1 12。 示例 3 输入 [2,1,4,5,3,1,1,3] 输出 12 解释 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约总时长 2 4 3 3 12。 3.问题分析 对于动态规划多状态这类问题看完题目后对于某个事物有明显几个状态比如这道题的事物就是这个按摩师这个按摩师可能有工作休息两种状态而我们要做的就是将这两种状态表示出来然后计算不同状态下他所能达到的值。 最后依据题目来求解最大值还是最小值。
状态表示先用一个dp[n]进行表示然后就会发现对于某一个位置来说这个位置的客人可能选可能不选不选可能就是在休息那么很明显用一个dp表是不能表示出这两种状态的。所以状态表示可以如下f[i] 表⽰选择到 i 位置时 nums[i] 必选此时的最⻓预约时⻓ g[i] 表⽰选择到 i 位置时 nums[i] 不选此时的最⻓预约时⻓。状态转移方程对于f[i]数组来说选择到 i 位置时 nums[i] 必选此时的最⻓预约时⻓所以如果i位置必选那么i-1就不能再选刚好g[i] 表示的就是 nums[i] 不选此时的最⻓预约时此时f[i]nums[i] g[i-1] g[i]表示i位置不选那么i-1可以选也可以不选取这两者最大值g[i]max(f[i-1], g[i-1])。 所以状态表示分别为 f[i] nums[i] g[i - 1];g[i] max(f[i - 1], g[i - 1]);初始化对于f[i]来说i位置表示必选所以f[0]nums[0]对于g[i]来说i位置表示不选所以g[0]0 。填表顺序根据状态转移⽅程得从左往右两个表⼀起填。返回值根据状态表⽰应该返回max(f[n - 1], g[n - 1])。
代码如下
class Solution
{
public:int massage(vectorint nums) {int n nums.size();//判断是否为空if (n 0)return 0;vectorint f(n), g(n);//初始化f[0] nums[0];for (int i 1; i n; i){f[i] nums[i] g[i - 1];g[i] max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};2. 打家劫舍II medium
1.题目链接打家劫舍II 2.题目描述你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
示例 1 输入nums [2,3,2] 输出3 解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2,因为他们是相邻的。 示例 2 输入nums [1,2,3,1] 输出4 解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。偷窃到的最高金额 1 3 4 。 示例 3 输入nums [1,2,3] 输出3 3.问题分析 这道题上道题的区别就是将这个nums数组看作是一个环形数组这样的话就需要考虑临界区也就是对首尾的状况进行分析具体有如下几种如果第一个位置选那么最后一个位置就不能选也就是在区间[0,n - 2]如果最后一个位置选那么第一个位置就不能选也就是区间[1,n - 1]。 还有没有别的情况没有了。然后对两个区间[0,n - 2]和[1,n - 1]分别进行一次按摩师的问题就可以求出最大值。
状态表示f[i] 表⽰选择到 i 位置时 nums[i] 必选此时偷取利润的最大值 g[i] 表⽰选择到 i 位置时 nums[i] 不选此时偷取利润的最大值。状态转移方程如按摩师的分析方式状态转移方程如下 f[i] nums[i] g[i - 1];g[i] max(f[i - 1], g[i - 1]);初始化对于f[i]来说i位置表示必选所以f[0]nums[0]对于g[i]来说i位置表示不选所以g[0]0 。填表顺序根据状态转移⽅程得从左往右两个表⼀起填。返回值根据状态表⽰应该返回max(f[n - 1], g[n - 1])。
代码如下
class Solution
{
public:int _rob(vectorint nums, int left, int right){if (left right)return 0;int n nums.size();vectorint f(n), g(n);//初始化第一个值f[left] nums[left];for (int i left 1; i right; i){f[i] nums[i] g[i - 1];g[i] max(f[i - 1], g[i - 1]);}return max(f[right], g[right]);}int rob(vectorint nums) {int n nums.size();//判断临界条件if (n 1)return nums[0];//分别求出两个区间[0,n - 2]和[1,n - 1]的最大值return max(_rob(nums, 0, n - 2), _rob(nums, 1, n - 1));}
};3. 删除并获得点数medium
1.题目链接删除并获得点数 2.题目描述 给你一个整数数组 nums 你可以对它进行一些操作。 每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除 所有 等于 nums[i] - 1 和 nums[i] 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1 输入nums [3,4,2] 输出6 解释 删除 4 获得 4 个点数因此 3 也被删除。 之后删除 2 获得 2个点数。总共获得 6 个点数。 示例 2 输入nums [2,2,3,3,3,4] 输出9 解释 删除 3 获得 3 个点数接着要删除两个 2 和 4 。 之后再次删除3 获得 3 个点数再次删除 3 获得 3 个点数。 总共获得 9 个点数。 提示 1 nums.length 2 * 10^4 1 nums[i] 10^4 3.问题分析 这道题就需要很好的理解能力了大概意思是给你一个数组然后你可以删除一个元素并获得它的大小这里就叫做点数但是你如果删除了某个数比如5那么你就不能再删除数组中的3和4上述加红区域。看到这会想到什么是不是就和上述第一题差不多了i位置必选的话i-1与i1位置就不能再选。然后就需要一些操作将本题变为与上述题一样的解法即可思路如下由提示可知道1 nums[i] 10^4所以用一个10001大小的数组将数据管理起来下标对应的就是每个数据所存的元素表示该下标总共的和例如4出现3次那么4的位置所存的数据就为12。
状态表示如上题一样用f[i]表示i位置删除所获取的最大点数g[i]表示i位置不删除所获取的最大点数。状态转移方程如按摩师的分析方式状态转移方程如下 f[i] hash[i] g[i - 1];g[i] max(f[i - 1], g[i - 1]);初始化对于f[0]位置来说必选后值为0。填表顺序从左往右两表一次填写。返回值max(f[N - 1], g[N - 1])。
代码如下
class Solution
{
public:int deleteAndEarn(vectorint nums) {const int N 10001;int hash[N] { 0 };for (auto x : nums)hash[x] x;vectorint f(N), g(N);for (int i 1; i N; i){f[i] hash[i] g[i - 1];g[i] max(f[i - 1], g[i - 1]);}return max(f[N - 1], g[N - 1]);}
};4. 买卖股票的最佳时机含冷冻期medium
1.题目链接买卖股票的最佳时机含冷冻期 2.题目描述给定一个整数数组prices其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:
卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1: 输入: prices [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 示例 2: 输入: prices [1] 输出: 0 提示 1 prices.length 5000 0 prices[i] 1000 3.问题分析 这类题先分状态然后对每种状态再进行详细讨论。如本题状态该怎么分在某一天的交易状态可能为买入、冷冻期冷冻期之后为可交易状态可交易状态是需要自行找出的因为卖出的那一刻和进入冷冻期的利润相同所以买卖股票问题不需要关心卖出状态如果考虑卖出状态的话要记得冷冻期的利润是和当天卖出状态利润相同的。
状态表示由于有「买⼊」「可交易」「冷冻期」三个状态因此我们可以选择⽤三个数组其中dp[0][j] 表⽰第 i 天结束后处于「买⼊」状态此时的最⼤利润dp[1][j] 表⽰第 i 天结束后处于「冷冻期」状态此时的最⼤利润dp[2][j] 表⽰第 i 天结束后处于「可交易」状态此时的最⼤利润。状态转移方程由下图进行分析
箭头末尾表示昨天箭头前端表示今天。nothing表示什么也不用做。 由买入状态开始分析由买入能不能到买入状态什么也不干就可以由买入到冷冻期昨天卖出今天就到冷冻期 由买入到可交易买入后只能卖出到冷冻期所以不可行。 冷冻期状态由冷冻期到冷冻期不行由冷冻期到买入显而易见也不行由冷冻期到可交易昨天冷冻期什么也不干今天就能到达可交易。可交易状态由可交易到可交易昨天可交易状态什么也不干今天就又是可交易状态由可交易到买入昨天可交易今天当然可以买入由可交易到冷冻期不行。 所以状态转移方程如下dp[0][j] max(dp[0][j - 1], dp[2][j - 1] - prices[j]); dp[1][j] dp[0][j - 1] prices[j]; dp[2][j] max(dp[2][j - 1], dp[1][j - 1]);
初始化三种状态都会⽤到前⼀个位置的值因此需要初始化每⼀⾏的第⼀个位置 dp[0][0] 此时要想处于「买⼊」状态必须把第⼀天的股票买了因此 dp[0][0] -prices[0] dp[1][0] 啥也不⽤⼲即可因此 dp[1][0] 0 dp[2][0] ⼿上没有股票买⼀下卖⼀下就处于冷冻期此时收益为 0 因此 dp[2][0] 0 。填表顺序从上到下从左往右三个表⼀起填。返回值买入状态的利润肯定不是最大的所以返回冷冻期状态或可交易状态的最大值即可。
代码如下
class Solution
{
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(3, vectorint(n));dp[0][0] -prices[0];for (int j 1; j n; j){dp[0][j] max(dp[0][j - 1], dp[2][j - 1] - prices[j]);dp[1][j] dp[0][j - 1] prices[j];dp[2][j] max(dp[2][j - 1], dp[1][j - 1]);}return max(dp[1][n - 1], dp[2][n - 1]);}
};5. 买卖股票的最佳时机IIIhard
1.题目链接买卖股票的最佳时机III 2.题目描述给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔k笔 交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 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 提示 1 prices.length 10^5 0 prices[i] 10^5 3.问题分析 这道题与上道题相比多需要考虑一个交易次数所以需要再增加一个维度用来表示交易次数。对于状态来说只有买入状态和可交易状态所以用fg两个数组来进行表示第二个维度j表示的就是交易次数。
状态表示f[i][j] 表⽰第 i 天结束后完成了 j 次交易处于「买⼊」状态此时的最⼤利润 g[i][j] 表⽰第 i 天结束后完成了 j 次交易处于「卖出」状态此时的最⼤利润。状态转移⽅程 对于 f[i][j] 有两种情况到这个状态 在 i - 1 天的时候交易了 j 次处于「买⼊」状态第 i 天啥也不⼲即可。此时最⼤利润为 f[i - 1][j] 在 i - 1 天的时候交易了 j 次处于「卖出」状态第 i 天的时候把股票买了。此时的最⼤利润为 g[i - 1][j] - prices[i] 。综上所求的是「最⼤利润」因此是两者的最⼤值 f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]) 。 对于 g[i][j] 有两种情况可以到达这个状态 在 i - 1 天的时候交易了 j 次处于「卖出」状态第 i 天啥也不⼲即可。此时的最⼤利润为 g[i - 1][j] 在 i - 1 天的时候交易了 j - 1 次处于「买⼊」状态第 i 天把股票卖了然 后就完成了 j ⽐交易。此时的最⼤利润为 f[i - 1][j - 1] prices[i] 。但是这个状态不⼀定存在要先判断⼀下。要求的是最⼤利润因此状态转移⽅程为g[i][j] g[i - 1][j]; if(j 1) g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]);初始化 由于需要⽤到 i 0 时的状态因此初始化第⼀⾏即可。 当处于第 0 天的时候只能处于「买⼊过⼀次」的状态此时的收益为 -prices[0] 因此 f[0][0] - prices[0] 。 为了取 max 的时候⼀些不存在的状态「起不到⼲扰」的作⽤我们统统将它们初始化为 -INF ⽤ INT_MIN 在计算过程中会有「溢出」的⻛险这⾥ INF 折半取0x3f3f3f3f ⾜够⼩即可溢出情况当初始化为负无穷时-prices[0]-oo就会溢出。填表顺序从上往下填每⼀⾏每⼀⾏从左往右两个表⼀起填。返回值返回每次交易的最大值。
代码如下
class Solution {
public:const int INF 0x3f3f3f3f;int maxProfit(vectorint prices) {int n prices.size();vectorvectorint f(n, vectorint(3, -INF)), g(n, vectorint(3, -INF));f[0][0] -prices[0], g[0][0] 0;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]);if (j 1) //防止越界g[i][j] max(g[i - 1][j], f[i - 1][j - 1] prices[i]);else g[i][j] g[i - 1][j];}}int ret 0;for (int j 0; j 3; j)ret max(ret, g[n - 1][j]);return ret;} } ;对于买卖股票的最佳时机IV问题来说交易k次分析方式与上道题基本无异只需将上述代码中的3改为k即可。
