将递归转换为循环或更优方案：寻求代码性能优化方法

嘿，针对你这个递归优化的问题，我整理了几个实用的方案，包括现有递归的优化点、循环实现的动态规划思路，还有其他高效技巧，一起来看看：

一、现有递归的 immediate 优化点 #

1. 修复记忆化的有效性问题 #

你当前用memo数组做记忆化，但默认初始值0是合法返回值（比如D<0时返回0），这会导致已计算的0结果被误判为未计算，重复执行递归。推荐调整：

• 把memo初始化为-1，用这个值标记「未计算的状态」
• 计算完成后再把结果存入memo，避免逻辑混淆

修改后的递归片段示例：

public static int MOD = 11380;
public static int[][][][] memo = new int[11][11][11][31];

// 初始化memo为-1，标记未计算状态
static {
    for (int a = 0; a < 11; a++)
        for (int b = 0; b < 11; b++)
            for (int c = 0; c < 11; c++)
                Arrays.fill(memo[a][b][c], -1);
}

public static int solve(int L1, int L2, int L3, int D) {
    if (D < 0) { return 0; }
    if (L1 + L2 + L3 == 0) { return 1; }
    // 已计算过直接返回
    if (memo[L1][L2][L3][D] != -1) {
        return memo[L1][L2][L3][D];
    }
    int ret = 0;
    // 补全你的三层循环转移逻辑（这里假设每次递归消耗1步D）
    for (int i = 0; i < L1; ++i) {
        for (int j = 0; j <= L2; ++j) {
            for (int k = 0; k <= L3; ++k) {
                ret = (ret + solve(i, j, k, D - 1)) % MOD;
            }
        }
    }
    // 计算完成后存入memo
    memo[L1][L2][L3][D] = ret;
    return ret;
}

2. 降低递归栈开销 #

递归本身会产生栈帧创建、销毁的开销，对于多层递归场景，可以尝试：

• 用栈模拟递归过程（非递归记忆化搜索）
• 直接转成迭代式动态规划，这是效率最高的方案

二、转换为循环实现的动态规划（DP） #

你的状态(L1, L2, L3, D)是完全可以用迭代推导的，因为每个状态的结果都依赖于更小的子状态，适合用DP迭代填充。

1. 状态定义 #

dp[l1][l2][l3][d]：含义和递归的solve(l1,l2,l3,d)完全一致，即剩余l1、l2、l3资源，还有d步时的合法方案数。

2. 基础状态初始化 #

• 当所有资源耗尽（l1+l2+l3=0），不管剩余多少步（d>=0），方案数都是1：dp[0][0][0][d] = 1
• 当d<0时所有状态为0，迭代时通过循环边界规避即可

3. 迭代实现示例 #

public static int MOD = 11380;

public static int dpSolve(int initL1, int initL2, int initL3, int initD) {
    // 初始化四维DP数组
    int[][][][] dp = new int[11][11][11][31];
    
    // 填充基础状态
    for (int d = 0; d <= 30; d++) {
        dp[0][0][0][d] = 1;
    }
    
    // 按步长d从小到大迭代，确保计算当前d时，d-1的状态已完成
    for (int d = 0; d <= 30; d++) {
        for (int l1 = 0; l1 <= 10; l1++) {
            for (int l2 = 0; l2 <= 10; l2++) {
                for (int l3 = 0; l3 <= 10; l3++) {
                    if (l1 + l2 + l3 == 0) continue; // 基础状态已初始化
                    int ret = 0;
                    // 补全和递归一致的转移逻辑
                    for (int i = 0; i < l1; ++i) {
                        for (int j = 0; j <= l2; ++j) {
                            for (int k = 0; k <= l3; ++k) {
                                if (d - 1 >= 0) {
                                    ret = (ret + dp[i][j][k][d - 1]) % MOD;
                                }
                            }
                        }
                    }
                    dp[l1][l2][l3][d] = ret;
                }
            }
        }
    }
    
    // 返回目标状态的结果
    return dp[initL1][initL2][initL3][initD];
}

4. 空间优化：降维处理 #

如果计算第d层只需要第d-1层的数据，可以把四维数组优化为两个三维数组：

• prevDp：存储上一步（d-1）的状态
• currDp：存储当前步（d）的状态
  这样空间占用从11*11*11*31≈39k降到2*11*11*11≈2.6k，内存紧张时非常实用。

三、其他高效技巧 #

• 预处理转移表：如果三层循环的转移逻辑固定，可以提前预处理转移权重，避免每次循环重复计算
• 剪枝优化：在递归或迭代中，提前跳过不可能产生有效结果的状态（比如剩余步数d不足以消耗完剩余资源时，直接返回0）

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