118. 杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

class Solution {
public:
  vector<vector<int>> generate(int numRows) {
    if (numRows == 1)
      return {{1}};

    vector<vector<int>> Result{{1}, {1, 1}};
    auto Last = Result.rbegin();
    for (int i = 3; i <= numRows; ++i) {
      vector<int> This(i);
      This[0] = 1; This[i - 1] = 1;
      for (int j = 1; j < i - 1; ++j)
        This[j] = (*Last)[j - 1] + (*Last)[j];

      Result.push_back(std::move(This));
      Last = Result.rbegin();
    }

    return Result;
  }
};

其实我这个写法完全就是当成模拟来写了。纯正的 DP 写法应该如下：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};

说实话这个写法还好懂一点，尤其是你能看到二维的状态转移方程

$$ f(i, j) = f(i-1, j) + f(i-1, j-1) $$

当然这道题其实应该把杨辉三角当成直角三角形来写，你会发现非常好想。

二刷

class Solution {
public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> Result;
    Result.emplace_back(1, 1);
    // Early return for the special case.
    if (numRows == 1)
      return Result;
    // else
    Result.emplace_back(2, 1);

    for (int i = 2; i < numRows; ++i) {
      Result.emplace_back(i + 1, 1);
      for (int j = 1; j < i; ++j)
        Result[i][j] = Result[i - 1][j - 1] + Result[i - 1][j];
    }
    return Result;
  }
};

这个emplace_back还是得多用才能熟练。顺便注意下这题有特例。