当前位置：首页 > article >正文

C++ 中的环形线性动态规划

article 2025/2/8 11:49:14

环形线性动态规划：从例题到算法实现

例题引入

问题描述：

假设你是一个小偷，计划在一个环形街区盗窃。街区共有 n 个房屋，每个房屋内有一定数量的现金。由于房屋是环形排列的，因此第一个房屋和最后一个房屋是相邻的。为了避免被发现，你不能盗窃相邻的两个房屋。请问，你最多能盗窃到多少现金？

示例：

输入: [2, 3, 2]
输出: 3
解释: 你不能盗窃第一个房屋和最后一个房屋，因为它们相邻。因此，你只能盗窃第二个房屋，获得 3 现金。

知识点介绍

动态规划（Dynamic Programming, DP）：

动态规划是一种用于解决具有重叠子问题和最优子结构性质的问题的算法设计方法。它将问题分解为子问题，通过保存子问题的解来避免重复计算，从而提高效率。

线性动态规划：

线性动态规划是指问题的状态转移方程只依赖于前一个或前几个状态的动态规划问题。通常，线性动态规划问题可以通过一维或二维数组来存储子问题的解。

环形动态规划：

环形动态规划是指问题在环形结构上进行状态转移的动态规划问题。由于环形结构的特殊性，通常需要将问题转化为线性动态规划问题来处理。

算法设计详细分析

问题分析：

在环形街区盗窃的问题中，由于房屋是环形排列的，因此第一个房屋和最后一个房屋是相邻的。这意味着如果我们选择盗窃第一个房屋，就不能盗窃最后一个房屋；反之亦然。因此，我们需要将问题分解为两个子问题：

不盗窃第一个房屋，只考虑从第二个房屋到最后一个房屋的线性排列。
不盗窃最后一个房屋，只考虑从第一个房屋到倒数第二个房屋的线性排列。

然后，我们分别对这两个子问题进行线性动态规划求解，最后取两个子问题的最大值作为最终结果。

状态定义：

设 dp[i] 表示盗窃到第 i 个房屋时能获得的最大现金。

状态转移方程：

对于线性动态规划问题，状态转移方程为：

$d p [i] = ma x (d p [i - 1], d p [i - 2] + n u m s [i])$

其中，dp[i-1] 表示不盗窃第 i 个房屋时的最大现金，dp[i-2] + nums[i] 表示盗窃第 i 个房屋时的最大现金。

边界条件：

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

环形处理：

为了处理环形结构，我们需要分别计算两个子问题的解：

不盗窃第一个房屋，计算 dp1，范围为 [0, n-1]。
不盗窃最后一个房屋，计算 dp2，范围为 [1, n]。

最后，取 max(dp1[n-1], dp2[n-2]) 作为最终结果。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minPathSum(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    if (n == 2) return min(nums[0], nums[1]);

    auto linearDP = [&](int start, int end) {
        vector<int> dp(n, 0);
        dp[start] = nums[start];
        dp[start + 1] = min(nums[start], nums[start + 1]);
        for (int i = start + 2; i < end; ++i) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + nums[i];
        }
        return dp[end - 1];
    };

    int excludeLast = linearDP(0, n - 1);
    int excludeFirst = linearDP(1, n);

    return min(excludeLast, excludeFirst);
}

int main() {
    vector<int> nums = {2, 3, 1, 5, 6, 4};
    cout << "The minimum path sum is: " << minPathSum(nums) << endl;
    return 0;
}

作业习题

将上述代码中的 min 替换成 max，求出路径总和最大的情况。
修改代码，使其可以处理站点之间存在负距离的情况。
如果小偷可以选择盗窃 k 个不相邻的房屋，如何设计动态规划算法？请给出状态定义和状态转移方程。

通过以上例题和习题的练习，相信你对环形线性动态规划有了更深入的理解。希望你能在实际问题中灵活运用这些知识，解决更多复杂的动态规划问题。

习题伪代码实现

1.路径总和最大的情况

function maxPathSum(nums):
    n = length(nums)  // 获取数组长度
    if n == 1: return nums[0]  // 若数组长度为1，直接返回唯一元素值
    if n == 2: return max(nums[0], nums[1])  // 若数组长度为2，返回较大值

    function linearDP(start, end):
        dp = array of size n  // 初始化动态规划数组
        dp[start] = nums[start]  // 初始状态
        dp[start + 1] = max(nums[start], nums[start + 1])  // 第二个状态
        for i from start + 2 to end - 1:
            dp[i] = max(dp[i - 1], dp[i - 2]) + nums[i]  // 状态转移方程
        return dp[end - 1]  // 返回最终状态

    excludeLast = linearDP(0, n - 1)  // 不包含最后一个元素的线性问题
    excludeFirst = linearDP(1, n)  // 不包含第一个元素的线性问题

    return max(excludeLast, excludeFirst)  // 返回两个结果中的较大值

2.处理负距离的情况

function minPathSumWithNegative(nums):
    n = length(nums)  // 获取数组长度
    if n == 1: return nums[0]  // 若数组长度为1，直接返回唯一元素值
    if n == 2: return min(nums[0], nums[1])  // 若数组长度为2，返回较小值

    function linearDP(start, end):
        dp = array of size n  // 初始化动态规划数组
        dp[start] = nums[start]  // 初始状态
        dp[start + 1] = min(nums[start], nums[start + 1])  // 第二个状态
        for i from start + 2 to end - 1:
            dp[i] = min(dp[i - 1], dp[i - 2]) + nums[i]  // 状态转移方程
        return dp[end - 1]  // 返回最终状态

    excludeLast = linearDP(0, n - 1)  // 不包含最后一个元素的线性问题
    excludeFirst = linearDP(1, n)  // 不包含第一个元素的线性问题

    return min(excludeLast, excludeFirst)  // 返回两个结果中的较小值

3.只能偷k个房屋

状态定义：

设 dp[i][j] 表示在前 i 个房屋中，选择盗窃 j 个不相邻房屋时能够获得的最大现金。

状态转移方程：

为了避免盗窃相邻房屋，小偷在选择盗窃第 i 个房屋时，前一个被选择盗窃的房屋只能在第 i-2 个或者更早。因此，我们有如下状态转移方程：

如果不盗窃第 i 个房屋：dp[i][j] = dp[i-1][j]
如果盗窃第 i 个房屋：dp[i][j] = dp[i-2][j-1] + nums[i]

综上所述，状态转移方程为：

$d p [i] [j] = ma x (d p [i - 1] [j], d p [i - 2] [j - 1] + n u m s [i])$

初始化和边界条件：

当 i = 0 时，无论选择盗窃多少个房屋，最大现金为 0：dp[0][j] = 0，其中 0 <= j <= k
当 j = 0 时，无论前面有多少个房屋，没有房屋被盗窃，最大现金为 0：dp[i][0] = 0，其中 0 <= i <= n
如果小偷要选择盗窃 1 个房屋，初始化时，我们有：dp[i][1] = nums[i]，其中 0 <= i < n

伪代码实现：

function maxStolenAmount(nums, k):
    n = length(nums)
    if k == 0: return 0
    if n == 0: return 0

    // 初始化二维动态规划数组 dp
    dp = array of size (n, k+1) initialized to 0

    // 边界条件初始化
    for j from 0 to k:
        dp[0][j] = 0
    for i from 0 to n:
        dp[i][0] = 0

    // 处理 dp[i][1]
    for i from 0 to n:
        dp[i][1] = nums[i]

    // 状态转移
    for i from 1 to n-1:
        for j from 1 to k:
            if i >= 2:
                dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + nums[i])
            else:
                dp[i][j] = dp[i-1][j]

    // 返回结果
    maxAmount = 0
    for i from 0 to n-1:
        maxAmount = max(maxAmount, dp[i][k])
    return maxAmount