动态规划系列 | 状态机模型(上)| 练完这些就算入门了!

这篇具有很好参考价值的文章主要介绍了动态规划系列 | 状态机模型(上)| 练完这些就算入门了!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

核心思想

用状态机模型求解动态规划问题,就是将原始问题用状态机模型进行表示,即每个节点表示状态,每条边表示一个状态转移,边上的权值表示转移的代价或收益

状态机模型的目标是找到一条从初始状态出发,经过若干次状态转移,达到某个终止状态的路径,使得最终的结果值最大或最小

LeetCode-198. 打家劫舍

题目描述

原题链接

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

问题分析

状态定义

  • dp[i][0]:表示不偷窃第 i 家,前 i 家的最大收益。
  • dp[i][1]:表示偷窃第 i 家,前 i 家的最大收益。

状态转移

  • 若不偷窃第 i 家,则可以从dp[i-1][0]dp[i-1][0]转移过来,即dp[i][0] = max(dp[i-1][0], dp[i-1][1])
  • 若偷窃第 i 家,因为不能偷窃两间相邻的房屋,因此dp[i][1]只能从第 i-1 家没有被偷窃的状态转移过来,即dp[i][1] = dp[i-1][0] + nums[i]

对应的状态转移图如下:

动态规划 有限状态机,手撕算法,动态规划,算法,leetcode

状态压缩

观察上述状态压缩图,我们可以进一步将状态压缩到只有两个状态:

动态规划 有限状态机,手撕算法,动态规划,算法,leetcode

压缩后的状态转移方程:

  • dp[0] = max(dp[0], dp[1])
  • dp[1] = dp[0] + nums[i]

复杂度分析

时间复杂度为: O ( n ) O(n) O(n)

空间复杂度为: O ( 1 ) O(1) O(1)

程序代码

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(2, 0);
        dp[1] = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            int t = dp[0];
            dp[0] = max(dp[0], dp[1]);
            dp[1] = t + nums[i];
        }
        return max(dp[0], dp[1]);
    }
};

LeetCode-188. 买卖股票的最佳时机 Ⅳ

题目描述

原题链接

给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

问题分析

我们将股票买入记为一次新的交易的开始。

状态定义

  • dp[i][j][0]:第 i 天,正在进行第 j 次交易,手中没有持有股票
  • dp[i][j][1]:第 i 天,正在进行第 j 次交易,手中持有股票

状态转移

  • 若第 i 天,正在进行第 j 次交易,手中没有持有股票,则上一天可能正在进行第 j 次交易,且手中没有持有股票。或者上一天持有股票,并在第 i 天卖出,即dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
  • 若第 i 天,正在进行第 j 次交易,手中持有股票,则上一天可能正在进行第 j 次交易,且手中没有持有股票。或者上一天不持有股票,并在第 i 天买入,即dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])

状态转移图

动态规划 有限状态机,手撕算法,动态规划,算法,leetcode

状态压缩

上述的状态转化图可以进一步压缩:

动态规划 有限状态机,手撕算法,动态规划,算法,leetcode

压缩后的状态转移方程:

  • dp[j][0] = max(dp[j][0], dp[j][1] + prices[i])
  • dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i])

复杂度分析

时间复杂度: O ( n × k ) O(n×k) O(n×k)

空间复杂度: O ( 2 × k ) O(2×k) O(2×k)

程序代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(k+1, vector<int>(2, 0));
        
        for(int i = 1; i <= k; i++)  dp[i][1] = -prices[0];

        for(int i = 1; i < prices.size(); i++) {
            for(int j = k; j >= 1; j--) {
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]);
            }
        }

        return dp[k][0];
    }
};

LeetCode-309. 买卖股票的最佳时机含冷冻期

题目描述

给定一个整数数组prices,其中第 prices[i] 表示第 _i_ 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

问题分析

我们将股票买入记为一次新的交易的开始。

状态定义

  • dp[i][0]:第 i 天,手中没有持有股票第 1 天。
  • dp[i][1]:第 i 天,手中没有持有股票超天数大于等于 2。
  • dp[i][2]:第 i 天,手中持有股票。

状态转移

  • dp[i][0] = dp[i-1][2] + prices[i]:第 i 天,手中没有持有股票第一天,一定是第 i -1 天持有股票,并在第 i 天卖出。
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0]):第 i 天,手中没有持有股票天数大于等于 2。则上一状态可能是不持有股票天数大于等于 2(dp[i-1][1])或第 i -1 天是不持有股票第一天(dp[i-1][0])。
  • dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]):第 i 天,正在进行第 j 次交易,手中持有股票。则上一状态可能是持有股票(dp[i-1][2])或第 i-1 天不持有股票天数大于等于2,并在第 i 天买入股票,即dp[i-1][1] - prices[i]

状态转移图

动态规划 有限状态机,手撕算法,动态规划,算法,leetcode

状态压缩

上述状态机模型图可以进一步压缩:

动态规划 有限状态机,手撕算法,动态规划,算法,leetcode

压缩后的状态转移方程:

  • dp[0] = dp[2] + prices[i]
  • dp[1] = max(dp[0], dp[1])
  • dp[2] = max(dp[1] - prices[i], dp[2])

复杂度分析

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( 1 ) O(1) O(1)文章来源地址https://www.toymoban.com/news/detail-835259.html

程序代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(3, 0);

        dp[2] = -prices[0];

        for(int i = 1; i < n; i++) {
            int t0 = dp[0], t1 = dp[1], t2 = dp[2];
            dp[0] = t2 + prices[i];
            dp[1] = max(t0, t1);
            dp[2] = max(t1 - prices[i], t2);
        }

        return max(dp[0], dp[1]);
    }
};

到了这里,关于动态规划系列 | 状态机模型(上)| 练完这些就算入门了!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 运筹系列87:julia求解随机动态规划问题入门

    随机动态规划问题的特点是: 有多个阶段,每个阶段的随机性互不相关,且有有限个实现值 (finite realizations) 具有马尔可夫性质,即每个阶段只受上一个阶段影响,可以用状态转移方程来描述阶段与阶段之间的变化过程。 我们使用julia的SDDP算法包来求解随机动态规划问题。

    2024年01月16日
    浏览(43)
  • 动态规划入门(数字三角形模型)

    备战 2024年蓝桥杯算法学习 -- 每日一题 Python大学A组         试题一:摘花生         试题二:最低通行费用         试题三:方格取数         试题四:传纸条 【题目描述】         Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩

    2024年04月14日
    浏览(42)
  • 动态规划系列 | 最长上升子序列模型(下)| 拦截导弹一网打尽!

    题目描述 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。 某天,雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段,所以只有一套

    2024年02月03日
    浏览(50)
  • 第九章 动态规划part04(● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集 )

    ● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集 https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 视频讲解:https://www.bilibili.com/video/BV1cg411g7Y6 1.确定dp数组以及下标的含义 i是物品,j是背包容量

    2024年01月16日
    浏览(52)
  • 【动态规划】简单多状态

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

    2024年02月15日
    浏览(51)
  • 动态规划之简单多状态

    1.题目链接:按摩师 2.题目描述:一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。

    2024年02月09日
    浏览(41)
  • 动态规划——状态转移方程

    DP问题的核心即确定动态转移方程。 (1)寻找变量,确定子问题。DP表一般为二维,故需要两个变量。 (2)寻找总问题与子问题迭代关系,确定中间值、迭代值 例1: 有5个物品,其重量分别是{2, 2, 6, 5, 4},价值分别为{6, 3, 5, 4, 6},背包的容量为10,计算背包所能装入物品的

    2023年04月08日
    浏览(35)
  • Day42|动态规划part04: 01背包问题,你该了解这些!、滚动数组、416. 分割等和子集

    其他背包,面试几乎不会问,都是竞赛级别的了,leetcode上连多重背包的题目都没有,所以题库也告诉我们,01背包和完全背包就够用了。 而完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。 01 背包问题描述 有n件物品和一个最多能背重量为w 的背包

    2024年04月25日
    浏览(38)
  • 【算法学习】简单多状态-动态规划

            本篇博客记录动态规划中的简单多状态问题。         在之前的动态规划类型的题中,我们每次分析的都只是一种或者某一类的状态,定义的dp表也是围绕着一种状态来的。         现在可能对于一种状态,存在几种不同的子状态,在状态转移过程中相互影响。此时

    2024年01月18日
    浏览(41)
  • C++算法 —— 动态规划(3)多状态

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

    2024年02月09日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包