c++经典的递归案例：计算组合数（使用动态规划优化）

c++经典的递归案例：计算组合数（使用动态规划优化）

#include <iostream>

// 经典的递归案例：计算组合数（使用动态规划优化）
int binomialCoefficient(int n, int k, int** memo) {
    // 基本情况：如果k为0或k等于n，返回1
    if (k == 0 || k == n) {
        return 1;
    } else if (memo[n][k] != -1) {
        // 如果已经计算过组合数，直接返回存储的值
        return memo[n][k];
    } else {
        // 递归调用：计算组合数，并将结果存储在memo数组中
        memo[n][k] = binomialCoefficient(n - 1, k - 1, memo) + binomialCoefficient(n - 1, k, memo);
        return memo[n][k];
    }
}

int main() {
    // 计算组合数C(5, 2)
    const int n = 5;
    const int k = 2;
    int** memo = new int*[n + 1];

    // 初始化memo数组为-1
    for (int i = 0; i <= n; ++i) {
        memo[i] = new int[k + 1];
        for (int j = 0; j <= k; ++j) {
            memo[i][j] = -1;
        }
    }

    // 输出组合数C(5, 2)
    std::cout << "组合数 C(" << n << ", " << k << ") 是：" << binomialCoefficient(n, k, memo) << std::endl;

    // 释放动态分配的内存
    for (int i = 0; i <= n; ++i) {
        delete[] memo[i];
    }
    delete[] memo;

    return 0;
}