【多状态DP】打家劫舍 / 删除并获得点数 / 股票问题 / 李白打酒加强版 / mari和shiny

_小羊_

发布于 2025-04-09 08:52:11

1800

文章被收录于专栏：C++C++

面试题 17.16. 按摩师

面试题 17.16. 按摩师

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]);
    }
};

打家劫舍

打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        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(g[i - 1], f[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};

打家劫舍 II

打家劫舍 II

由于房屋是首尾相连的，第一个房间和最后一个房间只能二选一，也就是第一个房间选不选的问题，最后返回两种情况下的最大值。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        return max(nums[0] + myrob(nums, 2, n - 2), myrob(nums, 1, n - 1));
    }
    int myrob(vector<int>& nums, int l, int r)
    {
        if (r - l < 0) 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(g[i - 1], f[i - 1]);
        }
        return max(f[r], g[r]);
    }
};

删除并获得点数

删除并获得点数

对所有数据排序，然后根据下标做一次打家劫舍就OK。

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int m = nums[0];
        for (int e : nums)
            m = max(e, m);
        vector<int> v(m + 1), f(m + 1), g(m + 1);
        for (int e : nums) v[e]++;
        for (int i = 1; i <= m; i++)
        {
            f[i] = v[i] * i + g[i - 1];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[m], g[m]);
    }
};

粉刷房子

粉刷房子

第 i 个房子的颜色可以有三种状态：红色、蓝色、绿色。则可以用 dp[i][0]、dp[i][1]、dp[i][2] 分别表示粉刷到第 i 个房子的时候粉刷为红色、蓝色或绿色的最小花费。

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(dp[n][0], min(dp[n][1], dp[n][2]));
    }
};

空间优化版。

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<int> dp(3), tmp(3);
        for (int i = 0; i < n; i++)
        {
            tmp[0] = min(dp[1], dp[2]) + costs[i][0];
            tmp[1] = min(dp[0], dp[2]) + costs[i][1];
            tmp[2] = min(dp[0], dp[1]) + costs[i][2];
            dp = tmp;
        }
        return min(dp[0], min(dp[1], dp[2]));
    }
};

买卖股票的最佳时机含冷冻期

买卖股票的最佳时机含冷冻期

分析题意，对第i天来说可以有买入、卖出和冷冻期三种状态。分别用 dp[i][0]、dp[i][1]、dp[i][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]);
    }
};

买卖股票的最佳时机含手续费

买卖股票的最佳时机含手续费

这道题只有两种状态：买入和卖出。用 f[i] 表示第i天的状态为买入，g[i] 表示第i天的状态为卖出。最大利润一定是最后一天卖出了，也就是 g[n - 1]。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> f(n), g(n);
        f[0] = -prices[0] - fee;
        for (int i = 1; i < n; i++)
        {
            f[i] = max(f[i - 1], g[i - 1] - prices[i] - fee);
            g[i] = max(g[i - 1], f[i - 1] + prices[i]);
        }
        return g[n - 1];
    }
};

买卖股票的最佳时机 III

买卖股票的最佳时机 III

还是有两种状态买入和卖出，但本题最多只能完成两笔交易，则可以用 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]);
注意：由买入状态转移为卖出，算是完成了一笔交易，所以 f[i - 1][j - 1] 到 g[i][j] 状态转移时交易次数应该+1。

对于第0天来说，不可能完成1笔或2笔交易，因此它们的值是无意义的。初始化防止越界，并且要保证填表的正确，因为要取最大值，所以初始化为最够小的数。

关于初始化最小值，这里初始化成 INT_MIN 会越界，所以为了保险起见初始化的时候尽量以 0x3f3f3f3f 初始化。

最大利润一定是最后一天处于卖出状态，并且可能交易了0次，1次，2次都有可能。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int N = 0x3f3f3f3f;
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -N));
        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 > 0)
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int ret = 0;
        for (int i = 0; i < 3; i++)
            ret = max(ret, g[n - 1][i]);
        return ret;
    }
};

买卖股票的最佳时机 IV

买卖股票的最佳时机 IV

k的值可能大于prices.size()，可以取一个较小值k = min(k, n / 2)。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        k = min(k, n / 2);
        const int N = 0x3f3f3f3f;
        vector<vector<int>> f(n, vector<int>(k + 1, -N));
        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 > 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int ret = 0;
        for (int i = 0; i <= k; i++)
            ret = max(ret, g[n - 1][i]);
        return ret;
    }
};

李白打酒加强版

一般求合法的个数、顺序、排列、方案等且范围不是很大，大概率是用动态规划做。

本题的关键所在是：最后一次遇到花，且酒恰好喝完。

动态规划的两大要素：状态和转移。 状态：题中共有三个状态：店、花、酒。所以设 dp[i][j][k] 表示经过i家店，j朵花，壶里还有k斗酒的方案数。转移：假设李白的壶中此时有k斗酒，则此时的状态 dp[i][j][k] 可以由 dp[i-1][j][k/2] （上一次遇到的是店，但是需要注意此时的k必须是偶数，因为此时的k是由上一次遇到店翻倍而来）和 dp[i][j-1][k+1] （上一次遇到的是花）转移而来。

最后返回 dp[n][m-1][1]，因为要保证最后一次遇到的是花，且酒恰好还剩一斗。

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
// dp[i][j][k]表示经过i家店，j朵花，壶里还有k斗酒的方案总数 
int dp[110][110][110];

int main()
{
	int n, m;
	cin >> n >> m;
	dp[0][0][2] = 1;
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; k < m; k++)
			{
				if (k % 2 == 0 && i > 0)
				{
					dp[i][j][k] += (dp[i - 1][j][k / 2]) % mod; 
				}
				if (j > 0)
				{
					dp[i][j][k] += (dp[i][j - 1][k + 1]) % mod;
				}
			}
		}
	}
	cout << dp[n][m - 1][1] << endl;
	return 0;
 }

mari和shiny

mari和shiny

如果测试用例没有完全通过，一定要检查一下数据范围，不开long long真的会见祖宗。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    string str;
    cin >> n >> str;
    vector<long> s(n), h(n), y(n);
    s[0] = str[0] == 's';
    for (int i = 1; i < n; i++)
    {
        if (str[i] == 's') s[i] = s[i - 1] + 1;
        else s[i] = s[i - 1];
        if (str[i] == 'h') h[i] = s[i - 1] + h[i - 1];
        else h[i] = h[i - 1];
        if (str[i] == 'y') y[i] = h[i - 1] + y[i - 1];
        else y[i] = y[i - 1];
    }
    cout << y[n - 1] << endl;
    return 0;
}

滚动数组做空间优化：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    string str;
    cin >> n >> str;
    long s = 0, h = 0, y = 0;
    for (auto ch : str)
    {
        if (ch == 's') s++;
        else if (ch == 'h') h += s;
        else if (ch == 'y') y += h;
    }
    cout << y << endl;
    return 0;
}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-04-08，如有侵权请联系 cloudcommunity@tencent.com 删除