动态规划进阶：多状态模型与序列决策 | 极客日志

C++算法

动态规划进阶：多状态模型与序列决策

本文讲解动态规划中的多状态模型，通过打家劫舍和买卖股票系列题目演示状态拆分与状态机转移方法。核心在于将复杂约束拆解为互斥状态，利用状态转移方程消除后效性。涵盖环形数组处理、冷冻期限制及交易次数限制等进阶场景，提供 C++ 代码实现与逻辑解析。

Stephaine Walsh发布于 2026/3/270 浏览

动态规划进阶：多状态模型与序列决策

动态规划进阶：深度解析序列决策与状态机模型

在处理具有复杂限制条件的动态规划问题时，单一的状态定义往往难以涵盖所有决策分支。通过将每一天的局面拆解为多个互斥的快照（States），并利用状态机描述其间的转移逻辑，可以有效地消除后效性，使问题迎刃而解。

一、 '打家劫舍'模型：状态拆分的起点

这类题目的核心在于处理'相邻元素互斥'的约束。

题目：198.打家劫舍

198. 打家劫舍

状态表示：
- 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])：若不偷当前房，前一间房偷或不偷均可，取最大值即可。

初始化：f[0] = nums[0]，g[0] = 0。

打家劫舍

代码实现：

class Solution {
public:
    int rob(vector<int>& nums) {
        //跟按摩师一样
        int n = nums.size();
        vector<int> f(n);
        auto g = f;
        f[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            f[i] = g[i - ] + nums[i];
            g[i] = (f[i - ], g[i - ]);
        }
         (f[n - ], g[n - ]);
    }
};

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

class Solution {
public:
    int rob(vector<int>& nums) {
        //处理首位房子后确定进行打家劫舍的区间
        //转化为打家劫舍 1（找到可以进行打家劫舍 1 的区间）
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }

    int rob1(vector<int>& nums, int left, int right) {
        if (left > right) return 0;
        int n = nums.size();
        vector<int> f(n);
        auto g = f;
        f[left] = nums[left];
        for (int i = left + 1; i <= right; ++i) {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[right], g[right]);
    }
};

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums[nums.size() - 1] + 1; //加上 0 这个位置
        //将原数组的值累加到 v 的对应位置，之后就可以转变为打家劫舍
        vector<int> v(n);
        for (int i = 0, j = nums[0]; i < nums.size();) {
            if (nums[i] == j) v[j] += nums[i++];
            else ++j;
        }
        //打家劫舍
        vector<int> f(n);
        auto g = f;
        f[1] = v[1], g[1] = 0;
        for (int i = 2; i < n; ++i) {
            f[i] = g[i - 1] + v[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3, 0));
        //0 买入 1 可交易 2 冷冻期
        dp[0][0] = -prices[0]; //初始化第一个位置即可（1，2 都为 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]); //最大值不会在最后一天再买入
    }
};

class Solution {
    const int INF = 0x3f3f3f; //整形最大值的一半
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INF)); //避免数据溢出
        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) {
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        //答案在交易次数为 2 的那一行
        int ret = 0;
        for (int i = 0; i < 3; ++i) {
            ret = max(ret, g[n - 1][i]);
        }
        return ret;
    }
};