118.杨辉三角

两天宇宙人

2020-02-01

🚌递归实现

在实现递归函数之前，有两件重要的事情需要弄清楚:

递推关系：一个问题的结果与其子问题的结果之间的关系。

基本情况: 不需要进一步的递归调用就可以直接计算答案的情况。有时，基本案例也被称为 bottom cases，因为它们往往是问题被减少到最小规模的情况，也就是如果我们认为将问题划分为子问题是一种自上而下的方式的最下层。

一旦我们计算出以上两个元素，再想要实现一个递归函数，就只需要根据递推关系调用函数本身，直到其抵达基本情况。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > vec;
        for(int i = 0; i < numRows; ++i) {
            vec.push_back({});
            for(int k = 0; k <= i; ++k) {
                vec[i].push_back(helper(i + 1, k + 1));
            }
        }
        return vec;
    }
    int helper(int i, int j) {
        if(j == 1 || j == i) 
            return 1;
        return helper(i - 1, j - 1) + helper(i - 1, j);
    }
};

Time Limit Exceeded

14/15 cases passed (N/A)

Testcase

30

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > vec;
        for(int i = 0; i < numRows; ++i) {
            vec.push_back({});
            for(int k = 0; k <= i; ++k) {
                vec[i].push_back(helper(i + 1, k + 1, vec));
            }
        }
        return vec;
    }
    int helper(int i, int j, vector<vector<int> >& vec) {
        if(j == 1 || j == i) 
            return 1;
        return vec[i - 2][j - 2] + vec[i - 2][j - 1];
    }
};