环形DP | Qi

环形动态规划（Circular Dynamic Programming）是一种动态规划的应用，适用于解决环形问题，即问题中的元素或状态在某种意义上是循环的，首尾相连的。这类问题在动态规划中需要考虑元素之间的相互关系，以及环形带来的特殊情况。

一般来说，环形动态规划的核心思想是将环形问题转化为线性问题，然后通过适当的状态转移方程和边界条件来求解。以下是环形动态规划的一般步骤：

问题转化：将环形问题转化为线性问题。可以通过复制一份原始数据，将环形结构“展开”成线性结构，从而将问题转化为已知的线性动态规划问题。
定义状态：定义动态规划的状态，通常与问题的特性相关。对于环形问题，需要考虑首尾相连的情况，可能需要多设置一个状态来表示“首尾相连”的状态。
确定状态转移方程：根据问题的性质，确定状态之间的转移关系。考虑环形结构，需要确保转移关系在环形首尾相连的情况下也能正确地进行。
确定边界条件：环形问题的边界条件可能相对复杂，需要确保首尾相连的元素能够正确处理。这些边界条件可能需要在状态转移方程中单独处理。
计算顺序：通常从小规模问题开始，按照线性结构的顺序逐步计算状态，直到计算出整个环形结构的状态。

下面以一个具体问题为例，来说明环形动态规划的应用。假设有一个环形数组，每个元素代表一个房屋，每个房屋中有一定数量的金钱。由于房屋是环形排列的，意味着第一个和最后一个房屋也相邻。要求在不偷相邻房屋的情况下，计算可以偷到的最大金钱数。

public class CircularDPExample {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        }
        
        // Calculate the maximum amount that can be robbed if starting from the first house.
        int[] dp1 = new int[n];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; i++) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }
        
        // Calculate the maximum amount that can be robbed if starting from the second house.
        int[] dp2 = new int[n];
        dp2[1] = nums[1];
        for (int i = 2; i < n; i++) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
        }
        
        // The maximum amount that can be robbed will be the maximum of the two scenarios.
        return Math.max(dp1[n - 2], dp2[n - 1]);
    }

    public static void main(String[] args) {
        CircularDPExample example = new CircularDPExample();
        int[] nums = {2, 7, 9, 3, 1};
        int maxAmount = example.rob(nums);
        System.out.println("Maximum amount that can be robbed: " + maxAmount);
    }
}

在这个例子中，我们通过定义两个状态数组 dp1 和 dp2，分别表示从第一个房屋和第二个房屋开始偷窃时的最大金额。通过动态规划的思想，我们逐步计算出每个状态的最大金额，最终得到在不偷相邻房屋的情况下可以偷到的最大金钱数。

请注意，以上仅是环形动态规划的一个简单例子。实际应用中，问题可能会更加复杂，需要根据问题的具体情况来定义状态、状态转移方程和边界条件。