一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。
注意:本题相对原题稍作改动
示例 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。
dp[i]
选择到i
位置的时候,此时的最长预约时长。继续细化:划分为两种状态f[i]
表示选择到i
位置的时候,nums[i]
位置必选,此时最长预约时间最长;g[i]
表示选择到i
位置的时候,nums[i]
位置不选,此时最长预约时间最长。
i
个位置选:f[i]=g[i-1]+nums[i]
第i
个位置不选:g[i]=max(f[i-1],g[i-1])
,此时i-1
位置可选可不选。
f[0]=nuns[0]
,g[0]=0
max(f[n-1],g[n-1])
class Solution {
public:
int massage(vector<int>& nums) {
int n=nums.size();
if(n==0) return 0;
vector<int> f(n),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]);
}
};
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 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
提示:
1 <= nums.length <= 100 0 <= nums[i] <= 1000
选了第一个位置就不能选择最后一个位置的房屋,因为是一个环形的房屋,第一个和最后一个是相邻的。分为两种情况:选第一个位置:nums[0]+rob(2,n-2)
,第一个位置不选:rob(1,n-1)
。最终选择两种情况中最大值即可。
f[i]
表示偷到i
位置是,偷nums[i]
,此时的最大金额;g[i]
表示偷到i
位置是,不偷nums[i]
,此时的最大金额。
i
位置:f[i]=g[i-1]+nums[i]
不偷第i
位置:g[i]=max(f[i-1],g[i-1])
f[0]=nums[0]
g[0]=0
max(f[n-1],g[n-1])
class Solution {
int rob1(vector<int>& nums,int l,int r)
{
if(l>r) return 0;
int n=nums.size();
vector<int> f(n),g(n);
f[l]=nums[l];
for(int i=l+1;i<=r;i++)
{
f[i]=g[i-1]+nums[i];
g[i]=max(f[i-1],g[i-1]);
}
return max(f[r],g[r]);
}
public:
int rob(vector<int>& nums) {
int n=nums.size();
return max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
}
};
给你一个整数数组 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 个点数。
本道题需要先预处理一下:
记录nums
数组中的值放在arr
数组中,arr
数组下标对应nums
数组中的数字,arr
数组下标对应的内容是nums
数组中同一个数字的总和。
例如:nums = [2,2,3,3,3,4]
,那么arr[0,0,4,9,4]
剩下的就是动态规划问题,类似于打家劫舍,不再具体分析。
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
vector<int> arr(10001,0);
for(auto x:nums) arr[x]+=x;
vector<int> f(10001),g(10001);
f[0]=arr[0],g[0]=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(f[10000],g[10000]);
}
};
假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。 例如,costs[0][0] 表示第 0 号房子粉刷成红色的成本花费;costs[1][2] 表示第 1 号房子粉刷成绿色的花费,以此类推。 请计算出粉刷完所有房子最少的花费成本。
示例 1: 输入: costs = [[17,2,17],[16,16,5],[14,3,19]] 输出: 10 解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色。 最少花费: 2 + 5 + 3 = 10。
示例 2: 输入: costs = [[7,6,2]] 输出: 2
分析一下示例1,理解一下costs
数组的使用方法:
dp[i][0]
:表示粉刷到i
位置时,粉刷上红色,此时的最小花费
dp[i][1]
:表示粉刷到i
位置时,粉刷上蓝色,此时的最小花费
dp[i][2]
:表示粉刷到i
位置时,粉刷上绿色,此时的最小花费
i
位置刷红色:dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i][0]
i
位置刷蓝色:dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i][1]
i
位置刷绿色:dp[i][2]=min(dp[i-1][1],dp[i-1][2])+costs[i][2]
dp
表的最后一个值,并且是最小的。
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n=costs.size();
vector<vector<int>> dp(n+1,vector<int>(3));
for(int i=1;i<=n;i++)
{
dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
dp[i][2]=min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];
}
return min(min(dp[n][0],dp[n][1]),dp[n][2]);
}
};
给定一个整数数组prices,其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1: 输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2: 输入: prices = [1] 输出: 0
dp[i][0]
表示第i
天结束之后,处于买入状态,此时的最大利润
dp[i][1]
表示第i
天结束之后,处于可交易状态,此时的最大利润
dp[i][2]
表示第i
天结束之后,处于冷冻期状态,此时的最大利润
i-1
天处于买入状态,第i
天可以啥也不干;
如果第i-1
天处于可交易状态,第i
天可以处于买入状态;
如果第i-1
天处于冷冻期状态,第i
天无法可以处于买入状态,并且-price[i]
;
如果第i-1
处于买入状态,第i
天可以处于冷冻期,并且+price[i]
;
如果第i-1
处于可交易状态,第i
天依旧可以处于可交易状态,啥也不干;
如果第i-1
处于可交易状态,第i
天可以处于冷冻期状态
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i])
dp[i][1]=max(dp[i-1][1],dp[i-1][2])
dp[i][2]=dp(dp[i-1][0]+p[i]
dp[0][0]=-p[0]
dp[0][1]=0
dp[0][2]=0
max(dp[n-1][1],dp[n-1][2])
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
vector<vector<int>> dp(n,vector<int>(3));
dp[0][0]=-prices[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][2]);
dp[i][2]=dp[i-1][0]+prices[i];
}
return max(dp[n-1][1],dp[n-1][2]);
}
};
空间复杂度O(n),时间复杂度O(n)
给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。 你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。 返回获得利润的最大值。 注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
示例 1: 输入:prices = [1, 3, 2, 8, 4, 9], fee = 2 输出:8 解释:能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2: 输入:prices = [1,3,7,5,10,3], fee = 3 输出:6
f[i]
表示第i
天结束后,处于买入状态,此时最大利润
g[i]
表示第i
天结束后,处于卖出状态,此时最大利润f[i]=max(f[i-1],g[i-1]-p[i])
g[i]=max(g[i-1],f[i-1]+p[i]-fee)
f[0]=-p[0]
g[0]=0
g[n-1]
结果不可能是f[n-1]
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n=prices.size();
vector<int> f(n);
vector<int> g(n);
f[0]=-prices[0];
for(int i=1;i<n;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 g[n-1];
}
};
给定一个数组,它的第 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
f[i][j]
表示第i
天结束后,完成了j
次交易,此时处于买入状态下达到最大利润
g[i][j]
表示第i
天结束后,完成了j
次交易,此时处于卖出状态下达到最大利润
f[i][j]=max(f[i-1][j],g[i-1][j]-p[i])
g[i][j]=max(g[i-1][j],f[i-1][j-1]+p[i]
在f[i-1][j-1]
因为当天次数为j
,所以前一天交易次数为j-1
g
表中最后一行的最大值
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
vector<vector<int>> f(n,vector<int>(3,-0x3f3f3f3f));
auto g=f;
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]);
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 ans=0;
for(int i=0;i<3;i++)
{
ans=max(ans,g[n-1][i]);
}
return ans;
}
};
给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1: 输入:k = 2, prices = [2,4,1] 输出:2 解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
示例 2: 输入:k = 2, prices = [3,2,6,5,0,3] 输出:7 解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n=prices.size();
vector<vector<int>> f(n,vector<int>(k+1,-0x3f3f3f3f));
auto g=f;
f[0][0]=-prices[0],g[0][0]=0;
for(int i=1;i<n;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 ans=0;
for (int j = 0; j <= k; ++j) {
ans = max(ans, g[n-1][j]);
}
return ans;
}
};