卖萌的弱渣

I am stupid, I am hungry.

Pascal’s Triangle II

Given an index k, return the kth row of the Pascal’s triangle.

Example

given k = 3, Return [1,3,3,1].

Note:

Could you optimize your algorithm to use only O(k) extra space?

Solution

  • 每次循环开始前在dp前面插入１，ret[i] = ret[i]+ret[i+1],
(Pascal-Triangle2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ret = new ArrayList<Integer>();
        if(rowIndex < 0)
            return ret;

        for(int i=0;i<=rowIndex;i++){
            ret.add(0,1);
            for (int j=1;j<ret.size()-1;j++){
                ret.set(j,ret.get(j+1)+ret.get(j));
            }
        }
        return ret;
    }
}
  • Python
(Pascal-Triangle2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """

        dp = [1]*(rowIndex+1)

        for i in range(2, rowIndex+1):
            for j in range(1,i):
                dp[i-j] += dp[i-j-1]
        return dp