【动态规划】简单多状态

这篇具有很好参考价值的文章主要介绍了【动态规划】简单多状态。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划(简单多状态)

1. 按摩师

题目链接

  1. 状态表示

    dp[i]表示到i位置的时候预约的最大时长。但是这个题目我们可以选择接或不接。因此可以继续划分为两个子状态:

    • f[i]表示:到i位置时接受的最大时长
    • g[i]表示:到i位置时不接受的最大时长
  2. 状态转移方程

    【动态规划】简单多状态,动态规划,算法

  3. 初始化

    因为这个题目比较简单,所以不需要使用虚拟节点的方法,初始化是为了后面填表的时候不越界

    f[0] = nums[0], g[0] = 0

  4. 填表

    从左到右

  5. 返回值

    接受最后一个或者不接受的最大值

AC代码:文章来源地址https://www.toymoban.com/news/detail-617111.html

class Solution 
{
public:
    int massage(vector<int>& nums) 
    {
        int n = nums.size();
        if (n == 0) return 0;
        vector<int> f(n);
        auto g = f;
        f[0] = nums[0], g[0] = 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]);
    }
};

2. 打家劫舍 ||

题目链接

分析:

由于房间是连续的,也就是一个环,因此可以分类讨论:

  • 偷第一个时,第二个和最后一个不能偷
  • 不偷第一个,可以偷第二个和最后一个

因此只需要两种情况的最大值就可以

  1. 状态表示

    dp[i]表示偷到i时的最大金额,但是依然可以划分为两种情况偷或不偷

    f[i]表示偷i时的最大金额

    g[i]表示不偷i时的最大金额

  2. 状态转移方程

    【动态规划】简单多状态,动态规划,算法

  3. 初始化

    保证后续的填表不越界

  4. 填表

    从左到右,两个一起填

  5. 返回值

    最大值

AC代码:

class Solution 
{
public:
    int rob(vector<int>& nums) 
    {
        int x = 0, y = 0;
        int n = nums.size();
        x += nums[0];
        x += recursion(2, n - 2, nums);
        y += recursion(1, n - 1, nums);
        return max(x, y);
    }
    int recursion(int left, int right, vector<int> &v)
    {
        if (left > right) return 0;
        int n = v.size();
        vector<int> f(n);
        auto g = f;
        f[left] = v[left]; // 初始化
        for (int i = left + 1; i <= right; i++)
        {
            f[i] = g[i - 1] + v[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        return max(f[right], g[right]);
    }
};

3. 删除并获得点数

题目链接

分析:我们把所有数字的点数之和,放到一个数组当中,在进行一次打家劫舍就可以了

把原数组转换成一个新数组,新数组的下标i所对应的值为原数组的元素i在原数组中数字的总和,比如原数组[2, 2, 3, 3, 3, 4],转换为新数组就是[0, 0, 4, 9, 4]。在新数组中,下标0和1表示在原数组中没有0和1这两个数,新数组下标2的值是4,表示在原数组中,所有2的总和是4。转换的目的就是可以从新数组中得到删除nums[i]而得到的点数,也就是可以打劫的金额。因为删除nums[i]后,还要删除nums[i] + 1nums[i] - 1,在新数组中就意味着不能取相邻的元素,不能取相邻的元素和打家劫舍也是一样的。接下来就可以使用打家劫舍的方式解答了

AC代码:

class Solution 
{
public:
    const int N = 10001;
    int deleteAndEarn(vector<int>& nums) 
    {
        vector<int> arr(N);
        for (auto e : nums) arr[e] += e;
        vector<int> g(N);
        auto f = g;
        for (int i = 1; i < N; i++)
        {
            f[i] = g[i - 1] + arr[i];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        return max(g[N - 1], f[N - 1]);
    }
};

4. 粉刷房子

题目链接

  1. 状态表示

    dp[i]表示到i时,所需的最少费用。但是到i的时候可以有三种情况我们需要分三个子状态

    dp[i][0], dp[i][1], dp[i][2]

  2. 状态转移方程

    【动态规划】简单多状态,动态规划,算法

  3. 初始化

    采用虚拟节点的方式

  4. 填表

  5. 返回值

    返回三个表中的最小值

AC代码:

class Solution 
{
public:
    int minCost(vector<vector<int>>& costs) 
    {
        // 0: 红色 1:蓝色 2:绿色
        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];
        }
        int ret = INT_MAX;
        for (int i = 0; i < 3; i++)
        {
            ret = min(ret, dp[n][i]);
        }
        return ret;
    }
};

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

题目链接

  1. 状态表示

    dp[i]表示到i位置时的最大利润,但是到达i位置的时候仍然有3种子状态

    • dp[i][0],表示i过后处于买入状态
    • dp[i][1], 表示i过后处于可交易状态
    • dp[i][2],表示i过后处于冷冻期状态
  2. 状态转移方程

    像这种状态之间可以相互转换的,我们可以采用如下方法分析:

    【动态规划】简单多状态,动态规划,算法

  3. 初始化

    dp[0][0] = -prices[0], dp[0][1] = 0, dp[0][2] = 0

  4. 填表

    三张表同时填

  5. 返回值

    返回三中状态最后的最大值

AC代码:

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

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

题目链接

  1. 状态表示

    dp[i]表示到i位置的时候,最大的利润但是到i位置的时候是有两种状态的

    dp[i][0]:表示是买入状态

    dp[i][1]表示卖出状态

  2. 状态转移方程

    【动态规划】简单多状态,动态规划,算法

  3. 初始化

    刚开始如果是买入状态dp[0][0] = -prices[0]

  4. 填表

  5. 返回值

AC代码:

class Solution 
{
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        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][0] + prices[i] - fee);
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

7. 买卖股票的最佳时机 |||

题目链接

  1. 状态表示

    dp[i]表示到i位置的最大利润,但是还分为几个状态

    f[i][j]表示到i是第j次买入的最大利润

    g[i][j]表示到i是第j次买入的最大利润

  2. 状态转移方程

    【动态规划】简单多状态,动态规划,算法

  3. 初始化

    f[0][0] = -prices[0], g[0][0] = 0

  4. 填表

    从上往下,每一行从左到右

  5. 返回值

    卖出状态最后的几个中的最大值

AC代码:

class Solution 
{
public:
    const int N = 0x3f3f3f3f;
    int maxProfit(vector<int>& prices) 
    {
        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 - 1 >= 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;
    }
};

8. 买卖股票的最佳时机 IV

题目链接

  1. 状态表示

    还是分为两个子状态

    f[i][j]表示到i位置买入状态第j次买股票的最大利润

    g[i][j]表示到i位置卖出状态第j次买股票的最大利润

  2. 状态转移方程

    【动态规划】简单多状态,动态规划,算法

  3. 初始化

    f[0][0] = -prices[0], g[0][0] = 0

  4. 填表

    从上到下,从左到右

  5. 返回值

    返回所有行的最大值

AC代码:

class Solution {
public:
    const int N = 0x3f3f3f3f;
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        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 - 1 >= 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;
    }
};

到了这里,关于【动态规划】简单多状态的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【动态规划】简单多状态

    题目链接 状态表示 dp[i] 表示到i位置的时候预约的最大时长。但是这个题目我们可以选择接或不接。因此可以继续划分为两个子状态: f[i] 表示:到i位置时接受的最大时长 g[i] 表示:到i位置时不接受的最大时长 状态转移方程 初始化 因为这个题目比较简单,所以不需要使用

    2024年02月15日
    浏览(45)
  • 「动态规划」简单多状态dp问题

    以经典问题“打家劫舍”来解释简单多状态dp问题和解决方法 题目链接:打家劫舍I 这种问题就是在某一个位置有多个状态可以选择,选择 不同的状态 会影响 最终结果 在这道题中就是小偷在每一个房屋,可以选择偷或不偷,每一次选择都会影响最终偷窃金额 状态表示 因为

    2024年03月15日
    浏览(54)
  • c++--简单多状态动态规划问题

    PS:以下代码均为C++实现 1.按摩师  力扣 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟

    2024年02月14日
    浏览(49)
  • 【动态规划】简单多状态dp问题(2)买卖股票问题

    买卖股票问题 传送门:力扣309. 最佳买卖股票时机含冷冻期 题目: 1.1 题目解析 越难的dp问题,看示例只能起到了解题目的效果,一般推不出啥普遍的规律,所以接下来就是我们的算法原理,通过动归的思想去理解,才会豁然开朗! 1.2 算法原理 1.2.1 状态表示 我们需要通过经

    2024年02月12日
    浏览(56)
  • 算法提高-动态规划-状态机模型

    这题比较简单,主要是学习一下状态机的模版(如何定义状态,dp方程如何推导)。 再学一个知识点:线性dp(i由i-1递推过来)可以用滚动数组优化空间复杂度 限制购买天数 这里也是线性dp,当然可以用滚动数组优化,但是之前大盗阿福写过了,这里就朴素版本了 限制了卖

    2024年02月15日
    浏览(59)
  • C++算法 —— 动态规划(3)多状态

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月09日
    浏览(37)
  • 【动态规划】简单多状态dp问题(1)打家劫舍问题

    打家劫舍问题 传送门:面试题 17.16. 按摩师 题目: 1.1 题目解析 越难的dp问题,看示例只能起到了解题目的效果,一般推不出啥普遍的规律,所以接下来就是我们的算法原理,通过动归的思想去理解,才会豁然开朗! 1.2 算法原理 1.2.1 状态表示 我们需要通过经验 + 题目要求去

    2024年02月12日
    浏览(41)
  • 【动态规划专栏】专题三:简单多状态dp--------3.删除并获得点数

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:动态规划专栏 🚚代码仓库:小小unicorn的代码仓库🚚

    2024年03月22日
    浏览(42)
  • 【状态压缩】【动态规划】【C++算法】691贴纸拼词

    视频算法专题 动态规划汇总 状态压缩 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。 您想要拼写出给定的字符串 target ,方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意,你可以多次使用每个贴纸,每个贴纸的数量是无限的。 返回你需要拼

    2024年01月19日
    浏览(39)
  • 【算法 - 动态规划】原来写出动态规划如此简单!

    从本篇开始,我们就正式开始进入 动态规划 系列文章的学习。 本文先来练习两道通过 建立缓存表 优化解题过程的题目,对如何将 递归函数 修改成 动态规划 的流程有个基本的熟悉。 用最简单的想法完成题目要求的 递归 函数; 定义明确 递归函数 的功能!!! 分析是否存

    2024年02月21日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包