如何用Dynamic Programming优化三元组求和计数的递归解法？

问题分析 #

你当前的递归解法本质是暴力枚举所有三元组的可能，时间复杂度O(K³)，当K较大时效率极低。核心问题是大量重复计算相同状态：比如当处理到第2个变量、当前和为5时，不管第一个变量选了1还是2，后续的计算逻辑完全一致，但原递归会重复执行这些计算。

动态规划的核心就是缓存这些重复状态的结果，避免重复计算，将时间复杂度降到O(3*min(S, 3K))，远优于O(K³)甚至O(K²)。

方案1：自顶向下记忆化搜索（修改原递归） #

状态定义 #

定义memo[limit][sum]：表示当前选到第limit个变量（1≤limit≤3），当前累加和为sum时，能凑出目标和S的三元组数量。

优化思路 #

在原递归基础上，新增一个二维数组缓存已经计算过的状态结果，每次递归前先检查该状态是否已计算：

• 若已计算，直接返回缓存值
• 若未计算，执行原递归逻辑，将结果存入缓存后返回

代码实现 #

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

vector<vector<int>> memo;
int k_global, s_global;

int count_sum_dp(int limit, int sum) {
    if (sum > s_global) return 0;
    if (sum == s_global) return 1;
    if (limit > 3) return 0;
    
    // 检查缓存，避免重复计算
    if (memo[limit][sum] != -1) {
        return memo[limit][sum];
    }
    
    int counter = 0;
    for (int i = 0; i <= k_global; ++i) {
        if (sum + i > s_global) break; // 剪枝，提前终止
        counter += count_sum_dp(limit + 1, sum + i);
    }
    
    // 存入缓存
    memo[limit][sum] = counter;
    return counter;
}

// 对外调用接口
int count_triples(int k, int s) {
    if (s < 0 || s > 3 * k) return 0; // 边界情况直接返回
    k_global = k;
    s_global = s;
    // 初始化memo：limit范围1-3，sum范围0-s
    memo.assign(4, vector<int>(s + 1, -1));
    return count_sum_dp(1, 0);
}

方案2：自底向上迭代DP #

状态定义 #

定义dp[i][j]：用前i个变量（i=0,1,2,3），凑出和为j的方案数。

状态转移 #

• 初始状态：dp[0][0] = 1（用0个变量凑和为0，只有1种方案）
• 对于第i个变量（1≤i≤3），遍历所有可能的和j，再遍历该变量的取值t（0≤t≤min(K,j)）：
  dp[i][j] += dp[i-1][j - t]

代码实现 #

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

int count_triples_dp(int k, int s) {
    if (s < 0 || s > 3 * k) return 0;
    // dp[i][j]：前i个变量凑和为j的方案数
    vector<vector<int>> dp(4, vector<int>(s + 1, 0));
    dp[0][0] = 1;
    
    for (int i = 1; i <= 3; ++i) {
        for (int j = 0; j <= s; ++j) {
            for (int t = 0; t <= min(k, j); ++t) {
                dp[i][j] += dp[i-1][j - t];
            }
        }
    }
    
    return dp[3][s];
}

复杂度分析 #

两种DP方案的时间复杂度均为O(3*min(S, 3K))：

• 记忆化搜索中，每个(limit, sum)状态只会计算一次，总状态数最多为3*(S+1)
• 自底向上DP的三层循环中，最内层循环的总执行次数也是O(3*S)

对比原O(K³)的解法，当K远大于S时（比如K≥S），DP的时间复杂度会降到O(S)，效率提升非常明显。

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