零、写在前面

  为了逼迫督促大家学习，《算法零基础100讲》 设置了付费模式，博主每天会开一篇试读文（免费阅读全文），文章中会有一些与本文相关的练习题。也就是今天的题不刷掉，非付费玩家明天就看不了了。此所谓聚焦学习，从 「 我可以学 」 变成 「 我必须学 」。
  当然，也可以选择跳过，只是今天不看，明天就会开放下一篇。这 100 篇更新完，至少可以刷掉 300 题（作者每天会至少开放三个题），如果每天都打卡坚持下来，算法就妥妥的入门了。
  任何事情都是要靠坚持的，但是坚持这件事情本身就不容易，所以，我把它转化成了游戏的形式，任何有规则，有乐趣的行为都可以称之为游戏，如果你看到了这篇文章，想要加入我们的刷题行列，和群友一起打卡学习，那就赶紧 联系博主 吧。

一、概念定义

  这一节，我们简单了解一下组合数。数学上的组合数是用公式实现的，而程序实现过程中，为了避免乘法产生的溢出，一般采用的是递推的形式。

1、组合数定义

  组合数表示为 $C_n^m$，它的含义是：从 $n$ 个不一样的元素中，选择 $m$ 个元素的方案数。

2、组合数递推公式

  组合数的递推公式如下：

$$C_n^m=C_{n−1}^{m-1} + C_{n−1}^m$$

3、递推公式的理解

  可以理解为：含特定元素的组合有 $C_{n−1}^{m-1}$，不含特定元素的排列为 $C_{n−1}^m$。
  更加具体的，含有特定元素 $1$ 的情况下，则需要从剩下 $n-1$ 个元素中，再找 $m-1$ 个元素，即方案数为 $C_{n−1}^{m-1}$；而不含有特定元素 $1$ 的情况下，则是从剩下的 $n-1$ 个元素中，再找 $m$ 个元素，即方案数为 $C_{n−1}^m$。
  而这两种情况就代表了所有情况，加和就是原问题的方案数。

4、举例说明

  从 1，2，3，4，5 $(n = 5)$ 中取出 2 $(m = 2)$ 个元素的组合 $C_n^m$：

$$12 \ \ 13 \ \ 14 \ \ 15 \ \ 23 \ \ 24 \ \ 25 \ \ 34 \ \ 35 \ \ 45$$

  这些组合中要么含有元素 “1”，要么不含。

1）含有1

$$12 \ \ 13 \ \ 14 \ \ 15$$

把里面的 “1” 都去掉，得到：

$$2 \ \ 3 \ \ 4 \ \ 5$$

等价于从 2，3，4，5 $(n−1)$ 中取出1 $(m−1)$ 个元素的组合。

2）不含有1

$$23 \ \ 24 \ \ 25 \ \ 34 \ \ 35 \ \ 45$$

等价于从 2，3，4，5 $(n−1)$ 中取出 2 $(m)$ 个元素的组合。

  总方案数等于上面两种情况方案数之和，即 $C_n^m=C_{n−1}^{m-1}+C_{n−1}^m$。

5、边界处理

  考虑当 $n$ 和 $m$ 都等于 0 时，方案数就是一；而当 $n=m$ 时，方案也只有一种。

二、题目描述

  给定一个非负整数 $n$，生成 「 杨辉三角 」 的前 $n$ 行。在 「 杨辉三角 」 中，每个数是它左上方和右上方的数的和。

三、算法详解

  「 杨辉三角 」 其实就是组合数，我们把这个上图的每个格子映射到一个二维数组中，自然就会发现，它和 $C_n^m$ 的递推公式不谋而合。

四、源码剖析

  以下是C语言版本，如果对 「 二级指针 」 还没有概念，建议使用 C++ 的 vector 。

int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    int i, j;
    int **ret = (int **)malloc(numRows * sizeof(int *));       // (1)
    *returnSize = numRows;                                     // (2)
    *returnColumnSizes = (int *)malloc(numRows * sizeof(int)); // (3)
    for(i = 0; i < numRows; ++i) {
        ret[i] = (int *)malloc( (i+1) * sizeof(int) );         // (4)
        (*returnColumnSizes)[i] = i+1;                         // (5)
        for(j = 0; j < i+1; ++j) {
            if(j == 0 || j == i) {
                ret[i][j] = 1;                                 // (6)
            }else {
                ret[i][j] = ret[i-1][j] + ret[i-1][j-1];       // (7)
            }
        }
    }
    return ret;
}

• $(1)$ 申请一个长度为numRows的二维数组，第二维是一个整型指针；
• $(2)$ 定义第一维的长度为numRows；
• $(3)$ 定义第二维的长度，由于第二维的每个元素长度不等，所以这里需要用一个数组；
• $(4)-(5)$ 申请第二维的内存空间，长度为 $i+1$；
• $(6)$ $ret[i][j]$ 代表了 $C_i^j$，处理边界情况；
• $(7)$ 递推公式；

五、推荐专栏

六、习题练习

请参考原文