题解 | #杨辉三角(二)#

题目分析

1. 题目给出一个数字num，其范围是0~33中任意一个整数
2. 在杨辉三角形中，第0行对应一个返回结果[1]，第1行对应返回结果[1,1]，第2行对应返回结果为[1,2,1]，第3行对应返回结果为[1,3,3,1]，以此按照杨辉三角的阵列规律表示。
3. 最终题目要求返回给出num的杨辉三角中对应行的数组结果。

方法一：动态规划递推

• 实现思路
  • 我们认为dp[i][j]表示下标为i的行中下标为j对应的杨辉三角中的某个数字
  • 其尊重的递推公式为
  • 依据递推公式得出如下代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型vector
     */
    vector<int> getRow(int num) {
        // write code here
        vector<vector<int>> dp;                            // 申请一个二维数组
        for(int i = 0; i <= num; i++) {
            vector<int> temp(i+1, 0);                      // 处理每一个新行
            temp[0] = 1;
            temp[i] = 1;                                   // 行首行尾元素填充为1
            if(num == 0) dp.push_back(temp);               // num=0情况特殊处理
            else {
                for(int j = 1; j < i; j++) {
                    temp[j] = dp[i-1][j-1] + dp[i-1][j];   // 递推
                }
                dp.push_back(temp);
            }
        }
        return dp[num];
    }
};

复杂度分析

• 时间复杂度：$O(nu{m}^2)O(num^2)$，由于在算法中有双重循环的时间开销，最后时间复杂度是num的平方级别
• 空间复杂度：$O(nu{m}^2)O(num^2)$，在算法中维护dp二位数组，因此空间代价是num的平方级别

方法二：动态规划的空间优化

• 实现思路
  • 由于在方法一中我们看到二维数组dp的递推关系只与相邻两行数据有关，因此只需要维护相邻两行的一维数组即可
  • 对于新的转移方程，我们有
  $cur[j]=pre[j-1]+pre[j];cur[j]\; =\; pre[j-1]\; +\; pre[j];$
  • 其中$curcur$表示当前行的内容，$prepre$表示上一行中的数据内容

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型vector
     */
    vector<int> getRow(int num) {
        // write code here
        vector<int> dp(1,1);                               // 对num=0情况处理
        if(num == 0) return dp;
        vector<int> pre = dp;
        for(int i = 1; i <= num; i++) {
            vector<int> cur(i+1, 0);                      // 处理每一个新行
            cur[0] = 1;
            cur[i] = 1;                                   // 行首行尾元素填充为1
            for(int j = 1; j < i; j++) {
                cur[j] = pre[j-1] + pre[j];               // 递推
            }
            pre = cur;									  // 将当前的cur赋值为下一轮的pre
        }
        return pre;
    }
};

复杂度分析

• 时间复杂度：$O(nu{m}^2)O(num^2)$，由于在算法中有双重循环的时间开销，最后时间复杂度是num的平方级别
• 空间复杂度：$O(num)O(num)$，算法优化了空间开销，只维护一维数组，因此空间代价是线性的