LeetCode OJ:Pascal's Triangle II

Pascal's Triangle II

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

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

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

算法思想：dp[row][col]保存row行col列元素值，则有dp[row][col]=dp[row-1][col-1]+dp[row-1][col];

可以用一维数组替代二维数组，不过j要从后向前遍历

class Solution {
public:
    vector
  
    getRow(int rowIndex) {
        vector
   
     dp(rowIndex+1); dp[0]=1; for(int i=1;i<=rowIndex;i++){ for(int j=i;j>=0;j--){ if(!j)continue; if(j==i){dp[j]=dp[j-1];continue;} dp[j]+=dp[j-1]; } } return dp; } };