如何将统计板球得分路径的递归函数转换为迭代或动态规划(DP)实现

优化思路 #

直接用补集转化简化问题：

• 所有可能的投球序列总数为 7^balls（每个投球有0~6共7种得分可能）
• 我们需要排除的仅为「投完全部balls个球后，总得分仍低于目标值target」的无效序列
• 最终答案 = 总序列数 - 无效序列数
  这种方式完全规避了提前达标的边界处理问题，非常适合用动态规划实现。

DP状态定义 #

定义 dp[i][j] 为投完i个球，恰好得到j分的方案数：

• 边界条件：dp[0][0] = 1（0个球得0分仅1种方案）
• 转移方程：对于第i个球的得分k（0≤k≤6），有 dp[i][j] += dp[i-1][j-k]（仅当j≥k时生效）
• 无效序列总数为 dp[balls][0] + dp[balls][1] + ... + dp[balls][min(target-1, 6*balls)]

优化实现（空间压缩版） #

因为计算第i轮状态仅依赖第i-1轮的结果，我们可以用一维数组滚动更新，空间复杂度从O(balls*target)降到O(target)。

代码实现 #

public class ScoreWaysCalculator {
    public static long calculateWays(int target, int balls) {
        // 边界情况：目标分0直接返回1
        if (target <= 0) return 1;
        // 最大可能得分超过目标时，仅需要计算到target-1即可
        int maxScore = Math.min(6 * balls, target - 1);
        long[] dp = new long[maxScore + 1];
        dp[0] = 1;

        for (int i = 0; i < balls; i++) {
            long[] nextDp = new long[maxScore + 1];
            for (int s = 0; s <= maxScore; s++) {
                if (dp[s] == 0) continue;
                for (int k = 0; k <= 6; k++) {
                    if (s + k <= maxScore) {
                        nextDp[s + k] += dp[s];
                    }
                }
            }
            dp = nextDp;
        }

        // 计算无效序列总数
        long invalid = 0;
        for (long num : dp) {
            invalid += num;
        }

        // 计算总序列数 7^balls
        long total = 1;
        for (int i = 0; i < balls; i++) {
            total *= 7;
        }

        return total - invalid;
    }

    public static void main(String[] args) {
        // 测试用例：目标20分，10个投球
        System.out.println("Total ways: " + calculateWays(20, 10));
    }
}

复杂度说明 #

时间复杂度为O(balls * target)，空间复杂度为O(target)，对于target=20、balls=10的场景仅需几百次运算，性能对比原版递归有指数级提升。

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