Pascal's Triangle II[E,Array,Dynamic Programming]

https://leetcode.com/problems/pascals-triangle-ii/description/

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

 

Constraints:

• 0 <= rowIndex <= 33

 

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

 

1. Python

그냥 무지성으로 함 풀어 보았다.

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0 : return [1]
        elif rowIndex == 1 : return [1,1]
        
        temp = self.getRow(rowIndex-1)
        ans = [1]*(rowIndex+1)
        for i in range(1,rowIndex):
            ans[i]=temp[i-1]+temp[i]
        
        return ans

 

2. C++

DP를 이용해보는 방법. time 은 O(X^2) 이지만 space 는 O(X)이다.

파스칼 삼각형에서 각 row별 숫자가 더해지는 방법을 잘 이해해야 짜낼 수 있는 코드다.

알고리즘보단 일종의 수학영역

#include <vector>
using namespace std;
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        // Using Dynamic Programming
        vector<int> ans(rowIndex+1,1);
        for(int i=1;i<rowIndex;i++){
            for(int j=i;j>0;j--){
                ans[j] += ans[j-1];
            }
        }
        return ans;
    }
};

 

3. C

다시 한 번 Recursive하게 풀어 주었다.

Returnsize가 함수 호출때마다 바뀌어서 마지막 return때 다시 언급해줘야 하는 구찮음은 있음

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getRow(int rowIndex, int* returnSize) {
        *returnSize = rowIndex+1;
        int* arr = (int*)malloc((*returnSize)*sizeof(int));
        for(int i=0;i<*returnSize;i++){
            arr[i] = 1;
        }
        if(*returnSize==0 || *returnSize==1) return arr;
        else{
            int* temp = getRow(rowIndex-1,returnSize);
            for(int j=1;j<*returnSize;j++){
                arr[j] = temp[j-1]+temp[j];
            }
            free(temp);
            *returnSize = rowIndex+1;
            return arr;}
}