- 按摩师
状态表示:
dp[i]: 表示到i位置时的，最长预约时长
状态转移方程:
dp[i] = max(dp[0], dp[1], ..., dp[i-2]) + nums[i]
int massage(vector<int>& nums)
{
// 0.边界情况处理
if(nums.size() == 0) return 0;
else if(nums.size() == 1) return nums[0];
else if(nums.size() == 2) return max(nums[0], nums[1]);
// 1.dp数组
vector<int> dp(nums.size());
// 2.初始化
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
// 3.状态转移方程
for(int i = 2; i < dp.size(); ++i)
{
int max = dp[0];
for(int j = 1; j < i - 1; ++j)
{
if(dp[j] > max) max = dp[j];
}
dp[i] = max + nums[i];
}
// 4.返回值
int max = dp[0];
for(int j = 1; j < dp.size(); ++j)
{
if(dp[j] > max) max = dp[j];
}
return max;
}
状态表示:
dp[i]: 表示到i位置时的，最长预约时长
细化:
f[i]: 表示到i位置时，nums[i]必选，此时的最长预约时长
g[i]: 表示到i位置时，nums[i]不选，此时的最长预约时长
状态转移方程:
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1], g[i-1]);
int massage(vector<int>& nums)
{
// 0.边界情况处理
if(nums.size() == 0) return 0;
// 1.dp数组
vector<int> f(nums.size());
vector<int> g(nums.size());
// 2.初始化
f[0] = nums[0];
g[0] = 0;
// 3.状态转移方程
for(int i = 1; i < nums.size(); ++i)
{
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
// 4.返回值
return max(f.back(), g.back());
}
- 打家劫舍 II
通过分类讨论，将环形问题，转换为线性问题
状态表示:
dp[i]: 表示到i位置时，rob的最大金额
细化:
f[i]: 表示到i位置时，nums[i]必选，此时rob的最大金额
g[i]: 表示到i位置时，nums[i]不选，此时rob的最大金额
状态转移方程:
f[i] = g[i-1] + nums[i];
g[i] = max(f[i-1], g[i-1]);
int rob_helper(vector<int>& nums)
{
// 1.dp数组
vector<int> f(nums.size());
vector<int> g(nums.size());
// 2.初始化
f[0] = nums[0];
g[0] = 0;
// 3.状态转移方程
for(int i = 1; i < nums.size(); ++i)
{
f[i] = g[i - 1] + nums[i];
g[i] = max(f[i - 1], g[i - 1]);
}
// 4.返回值
return max(f.back(), g.back());
}
int rob(vector<int>& nums)
{
// 0.边界情况处理
if(nums.size() == 1) return nums[0];
else if(nums.size() == 2) return max(nums[0], nums[1]);
else if(nums.size() == 3) return max(max(nums[0], nums[1]), nums[2]);
vector<int> rob_first = vector<int>(nums.begin() + 2, nums.end() - 1);
vector<int> rob_not_first = vector<int>(nums.begin() + 1, nums.end());
return max(nums[0] + rob_helper(rob_first), rob_helper(rob_not_first));
}
- 删除并获得点数
问题转化:
将nums中的数统计到一个新数组v中，再在v中做一次“打家劫舍”问题即可
int deleteAndEarn(vector<int>& nums)
{
// 0.问题转化
int max_size = 0;
for(int e : nums)
{
if(e > max_size) max_size = e;
}
vector<int> v(max_size + 1);
for(int e : nums)
{
v[e] += e;
}
// 1.dp数组
vector<int> f(v.size());
vector<int> g(v.size());
// 2.初始化
f[0] = v[0];
g[0] = 0;
// 3.状态转移方程
for(int i = 1; i < v.size(); ++i)
{
f[i] = g[i - 1] + v[i];
g[i] = std::max(f[i - 1], g[i - 1]);
}
// 4.返回值
return max(f.back(), g.back());
}
- 粉刷房子
状态表示:
dp[i][0]: 表示到i位置为止，粉刷成红色的最小花费
dp[i][1]: 表示到i位置为止，粉刷成蓝色的最小花费
dp[i][2]: 表示到i位置为止，粉刷成绿色的最小花费
状态转移方程:
dp[i][0] = min(dp[i-1][1], dp[i-1][2]);
dp[i][1] = min(dp[i-1][0], dp[i-1][2]);
dp[i][2] = min(dp[i-1][0], dp[i-1][1]);
int minCost(vector<vector<int>>& costs)
{
// 1.dp数组
vector<vector<int>> dp(costs.size(), vector<int>(3));
// 2.初始化
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
// 3.状态转移方程
for(int i = 1; i < dp.size(); ++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];
}
// 4.返回值
return min(min(dp.back()[0], dp.back()[1]), dp.back()[2]);
}
- 买卖股票的最佳时机含冷冻期
状态表示:
dp[i]: 表示第i天结束之后，此时的最大利润
dp[i][0]: 表示第i天结束后，处于买入状态时的最大利润
dp[i][1]: 表示第i天结束后，处于可交易状态时的最大利润
dp[i][2]: 表示第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];
int maxProfit(vector<int>& prices)
{
// 1.dp数组
vector<vector<int>> dp(prices.size(), vector<int>(3));
// 2.初始化
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
// 3.状态转移方程
for(int i = 1; i < dp.size(); ++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];
}
// 4.返回值
return max(dp.back()[1], dp.back()[2]);
}
- 买卖股票的最佳时机含手续费
状态表示:
dp[i][0]: 表示第i天结束后，处于买入状态时的最大利润
dp[i][1]: 表示第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);
int maxProfit(vector<int>& prices, int fee)
{
// 1.dp数组
vector<vector<int>> dp(prices.size(), vector<int>(2));
// 2.初始化
dp[0][0] = -prices[0];
dp[0][1] = 0;
// 3.状态转移方程
for(int i = 1; i < dp.size(); ++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);
}
// 4.返回值
return dp.back()[1];
}
- 买卖股票的最佳时机 III
状态表示:
dp[i]: 表示第i天结束之后，此时获得的最大利润
f[i][j]: 表示第i天结束之后，此时已完成j次交易，且处于“持有”股票状态的最大利润
g[i][j]: 表示第i天结束之后，此时已完成j次交易，且处于“未持有”股票状态的最大利润
状态转移方程:
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]);
int maxProfit(vector<int>& prices)
{
// 1.dp数组
vector<vector<int>> f(prices.size(), vector<int>(3, -0x3f3f3f3f));
vector<vector<int>> g(prices.size(), vector<int>(3, -0x3f3f3f3f));
// 2.初始化
f[0][0] = -prices[0];
g[0][0] = 0;
// 3.状态转移方程
for(int i = 1; i < prices.size(); ++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 >= 0)
g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]);
else
g[i][j] = g[i-1][j];
}
}
// 4.返回值
int ret = g.back()[0];
for(int i = 1; i < 3; ++i)
{
if(g.back()[i] > ret) ret = g.back()[i];
}
return ret;
}
- 买卖股票的最佳时机 IV
int maxProfit(int k, vector<int>& prices)
{
// 0.细节处理
k = min(k, (int)prices.size() / 2);
// 1.dp数组
vector<vector<int>> f(prices.size(), vector<int>(k + 1, -0x3f3f3f3f));
vector<vector<int>> g(prices.size(), vector<int>(k + 1, -0x3f3f3f3f));
// 2.初始化
f[0][0] = -prices[0];
g[0][0] = 0;
// 3.状态转移方程
for(int i = 1; i < prices.size(); ++i)
{
for(int j = 0; j < k + 1; ++j)
{
f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);
if(j - 1 >= 0)
g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]);
else
g[i][j] = g[i-1][j];
}
}
// 4.返回值
int ret = g.back()[0];
for(int i = 1; i < k + 1; ++i)
{
if(g.back()[i] > ret) ret = g.back()[i];
}
return ret;
}