用动态规划算法求组合数C r n ​ 。 例如，输入：5 3 则输出：10

动态规划是一种解决问题的方法，它通过将问题分解为更小的子问题，并将这些子问题的解存储起来，以避免重复计算，从而提高效率。在计算组合数C(n, r)时，我们可以使用动态规划的思想来实现。组合数C(n, r)表示从n个不同元素中取出r个元素的所有组合的数目。

根据定义，组合数C(n, r)可以通过以下公式计算： $C(n, r) = C(n - 1, r - 1) + C(n - 1, r)$ 这个公式说明了组合数C(n, r)等于从n-1个元素中取出r-1个元素的组合数加上从n-1个元素中取出r个元素的组合数1。

为了使用动态规划算法计算组合数，我们可以创建一个二维数组dp，其中dp[i][j]表示从i个元素中选择j个元素的组合数。基本情况是当k等于0或k等于n时，组合数为1，即C(n, 0) = C(n, n) = 189。

接下来，我们可以通过填充这个二维数组来实现动态规划计算组合数。数组dp有n+1行和r+1列，我们从基本情况开始，逐步填充数组，直到计算出C(n, r)的值。具体的实现步骤如下：

1. 初始化数组dp的大小为(n+1) x (r+1)。
2. 设置基本情况：对于所有的i（0 ≤ i ≤ n），dp[i][0] = 1 和 dp[i][i] = 1。
3. 使用嵌套循环填充数组：
   • 外层循环遍历行i（1 ≤ i ≤ n）。
   • 内层循环遍历列j（1 ≤ j ≤ r）。
   • 对于每个dp[i][j]，根据递推关系式计算其值：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。

例如，给定输入5和3，我们想要计算C(5, 3)。按照上述步骤，我们可以填充dp数组如下：

dp = [
  [1, 1, 1, 1, 1, 1],  // 第0列初始化为1
  [1, 1, 1, 1, 1, 1],  // 第1列初始化为1
  [1, 2, 1, 1, 1, 1],  // 第2列开始填充
  [1, 3, 3, 1, 1, 1],  // 第3列填充
  [1, 4, 6, 4, 1, 1]   // 第4列填充
]

最终，dp[5][3]的值即为C(5, 3)，即10。

通过这种方式，我们可以使用动态规划算法高效地计算出组合数C(n, r)。这种方法避免了暴力搜索中的重复计算，大大提高了计算效率456。