求含约束规则的7/19长度数组的合法组合数计算方案

问题描述 #

需要计算长度为7或19的数组的合法组合数量，具体信息如下：

• 初始数组：
  • 长度7：[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
  • 长度19：[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
• 数组每个位置的可选值（共10种）：0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5
• 约束规则：
  1. 索引0的元素最大值为3.5
  2. 索引1的元素最大值为4.0
  3. 相邻元素的差值不能超过2.5

已知组合数参考：

• 无约束时：长度7为10⁷，长度19为10¹⁹
• 仅满足规则1、2时：长度7为8×9×10⁵=7200000，长度19为8×9×10¹⁷=7200000000000000000

当前已实现仅考虑规则1、2的代码（使用bignumber.js处理大数精度），但加入规则3后，暴力枚举因计算量过大（长度19需10¹⁹次迭代）无法在合理时间内完成，现寻求高效计算方法。

当前实现代码 #

const BigNumber = require("bignumber.js");

const findCombinations = (n) => {
    let totalCombinations = BigNumber(1);

    for (let i = 1; i <= n; i++) {
        if (i === n) {
            totalCombinations = totalCombinations.times(8);
        } else if (i === n - 1) {
            totalCombinations = totalCombinations.times(9);
        } else {
            totalCombinations = totalCombinations.times(10);
        }
    }

    return totalCombinations;
};

console.log(findCombinations(7).toFixed());
console.log(findCombinations(19).toFixed());

高效解决方案：动态规划 #

核心思路 #

利用动态规划记录每个位置取特定值时的合法组合数，通过递推关系计算后续位置的状态，避免暴力枚举所有组合。

关键优化：值映射

将浮点数可选值转为整数（乘以2），简化差值判断：

• 0.0→0，0.5→1，...，4.5→9
• 相邻元素差值≤2.5等价于映射后的整数差值≤5

状态定义

设dp[i][v]表示数组第i个位置取映射值v时的合法组合数，其中v∈[0,9]。

状态转移

1. 初始化（i=0）：索引0最大值为3.5（映射值7），因此v∈[0,7]的dp[0][v] = 1，其余为0。
2. i=1：索引1最大值为4.0（映射值8），对每个v1∈[0,8]，dp[1][v1]等于所有满足|v1-v0|≤5的dp[0][v0]之和。
3. i≥2：每个位置可取所有10个值，对每个vi∈[0,9]，dp[i][vi]等于所有满足|vi-v_prev|≤5的dp[i-1][v_prev]之和。

空间优化

由于每次状态转移仅依赖前一个位置的状态，无需保存完整二维数组，仅用两个一维数组prevDp（记录上一位置状态）和currDp（计算当前位置状态）即可，空间复杂度降至O(1)。

实现代码 #

const BigNumber = require("bignumber.js");

// 可选值映射：0.0→0，0.5→1，...，4.5→9
const maxDiff = 5; // 对应2.5的差值（2.5*2=5）

const calculateValidCombinations = (n) => {
    if (n === 0) return BigNumber(0);

    // 初始化索引0的DP状态：最大值3.5对应映射值7，0-7每个值的组合数为1
    let prevDp = new Array(10).fill(BigNumber(0));
    for (let v = 0; v <= 7; v++) {
        prevDp[v] = BigNumber(1);
    }

    if (n === 1) {
        return prevDp.reduce((sum, num) => sum.plus(num), BigNumber(0));
    }

    // 处理索引1：最大值4.0对应映射值8
    let currDp = new Array(10).fill(BigNumber(0));
    for (let v1 = 0; v1 <= 8; v1++) {
        let sum = BigNumber(0);
        for (let v0 = 0; v0 < 10; v0++) {
            if (Math.abs(v1 - v0) <= maxDiff) {
                sum = sum.plus(prevDp[v0]);
            }
        }
        currDp[v1] = sum;
    }
    prevDp = currDp;

    if (n === 2) {
        return prevDp.reduce((sum, num) => sum.plus(num), BigNumber(0));
    }

    // 处理索引2到n-1的位置
    for (let i = 2; i < n; i++) {
        currDp = new Array(10).fill(BigNumber(0));
        for (let vi = 0; vi < 10; vi++) {
            let sum = BigNumber(0);
            for (let vPrev = 0; vPrev < 10; vPrev++) {
                if (Math.abs(vi - vPrev) <= maxDiff) {
                    sum = sum.plus(prevDp[vPrev]);
                }
            }
            currDp[vi] = sum;
        }
        prevDp = currDp;
    }

    // 总和为最后一个位置所有可能值的组合数之和
    return prevDp.reduce((sum, num) => sum.plus(num), BigNumber(0));
};

console.log("长度7的合法组合数：", calculateValidCombinations(7).toFixed());
console.log("长度19的合法组合数：", calculateValidCombinations(19).toFixed());

复杂度分析 #

• 时间复杂度：O(n×10×10) = O(n)，n=19时仅需1900次计算，可瞬间完成。
• 空间复杂度：O(1)，仅使用两个长度为10的数组，与n无关。

内容的提问来源于stack exchange，提问作者Rajohan