【动态规划】“好数组”计数问题

问题描述

我们有一个整数数组 A，长度为 N，其中每个数字都在 1 到 K 之间。我们需要找到满足以下条件的“好数组” B 的总数：

1. B[i] 的值必须在 1 到 K 之间。
2. 对于任意的 i（从 0 到 N−2），满足： B[i]+B[i+1]=A[i]+A[i+1]

思路讲解（适合小白）

这个问题乍看复杂，其实本质是“每个 B[i] 的值决定了下一个 B[i+1] 的取值范围”，也就是说：

1. 当前元素 B[i] 的选择，会影响到后面的选择。
2. 如果我们从头到尾遍历数组 A，每次都保存当前选择的结果，就能推导出整个数组 BB 满足条件的情况数。

所以，动态规划是一种非常合适的解法。

为什么用动态规划？

动态规划的两个重要特点：

1. 最优子结构：
   • 一个问题可以分解为更小的子问题，并且更小的子问题的解可以组合成整体问题的解。
   • 比如，知道前 ii 个元素 B[0],B[1],…,B[i] 的所有好数组组合数，我们就能推导出第 i+1 个元素的可能性。
2. 重叠子问题：
   • 计算当前 B[i] 的组合数时，会反复用到前一个位置 B[i-1] 的结果。
   • 动态规划通过保存中间结果（即用一个表记录已计算的值），避免了重复计算。

动态规划的设计步骤

1. 状态定义：
   我们用 dp[i][x]表示当数组 B 的第 i 个元素取值为 x 时，从 B[0] 到 B[i] 满足条件的好数组的组合数。

2. 状态转移：
   如果第 i 个元素 B[i]=x，则前一个元素 B[i-1] 的值 y 必须满足：

   y=A[i−1]+A[i]−x

   只要 y 在 1 到 K 的范围内，dp[i][x] 的值就可以从 dp[i−1][y] 继承。

3. 初始化：
   第一个元素 B[0] 可以是任何值，只要在 1 到 K 的范围内，所以：

   dp[0][x]=1(1≤x≤K)

4. 结果：
   最终结果是最后一个元素的所有可能值的组合数之和：

   结果=∑x=1Kdp[N−1][x]

代码实现（详细注释版）

public class GoodArrays {

    public static int countGoodArrays(int N, int K, int[] A) {
        // 创建一个二维数组来存储状态
        int[][] dp = new int[N][K + 1];

        // 初始化第一行
        for (int x = 1; x <= K; x++) {
            dp[0][x] = 1; // 第一个位置的每个值都是有效的
        }

        // 填充动态规划表
        for (int i = 1; i < N; i++) { // 遍历数组的位置
            for (int x = 1; x <= K; x++) { // 遍历当前可能的 B[i] 值
                int y = A[i - 1] + A[i] - x; // 计算前一个值 B[i-1] 的可能值
                if (y >= 1 && y <= K) { // 确保 y 在范围内
                    dp[i][x] += dp[i - 1][y]; // 累加前一个状态的结果
                }
            }
        }

        // 计算最终结果
        int result = 0;
        for (int x = 1; x <= K; x++) {
            result += dp[N - 1][x];
        }

        return result;
    }

    public static void main(String[] args) {
        // 测试样例
        System.out.println(countGoodArrays(3, 2, new int[]{1, 2, 1})); // 输出: 2
        System.out.println(countGoodArrays(4, 3, new int[]{1, 3, 2, 1})); // 输出: 1
        System.out.println(countGoodArrays(2, 1, new int[]{1, 1})); // 输出: 1
    }
}

博客首页：总是学不会