【新手上路】LeetCode刷题之杨辉三角（二）

几个星期前做了一道“伪动态规划”的题目杨辉三角一，现在来试试位于它下面的那道题目（二）

同样地，动画做得很好，只是我微薄的算法技巧配不上这么优秀的动画了，呜呜呜~。

以下是代码。

int* getRow(int rowIndex, int* returnSize){
    *returnSize = rowIndex+1;  //观察图片和例子不难发现，第几行它的个数就是行数+1，然后直接赋值就好
    int *result[rowIndex+1];
//因为我们是动态规划，所以我们在优化前必须要“升高维度”，要求我们返回一个一位数组，我们就得申请一个二维数组
    for(int i=0;i 
 其实吧，在CSDN写一遍过程和注释对算法的学习帮助会更大（让思路更清晰），毕竟像我这样不太聪明的人，学算法确实有点困难，坚持下去吧。
 
以下是Python的做法和解析：
 
class Solution:
    def getRow(self, rowIndex):
        result = [[1],[1,1]]  #和上次的类似，为了提高效率，前两种情况就手动写好了
        if rowIndex == 0:
            return result[0]
        elif rowIndex==1:
            return result[1]
        else:
            for i in range(2,rowIndex+2):  
                temp = [1,1]
                for j in range(i-2):
                    temp.insert(j+1,result[i-1][j]+result[i-1][j+1]) #dp表达式和之前差不多
                result.append(temp)  #把产生的新列表添加到末尾
        return result[rowIndex+1]
 
 
 
class Solution:
    def getRow(self, rowIndex):
        result = [[1],[1,1]]
        if rowIndex == 0:
            return result[0]
        elif rowIndex==1:
            return result[1]
        else:
            for i in range(2,rowIndex+2):
                temp = [1,1]
                for j in range(i-2):
                    temp.insert(j+1,result[i-1][j]+result[i-1][j+1])
                result.append(temp)
        return result[-1]
 
 
 
 
如果最后直接用索引-1的话，牺牲时间换空间，不太值得。