[알고리즘문제] 릿코드 Pascal's Triangle

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

Pascal's Triangle - LeetCode

input: integer number

output: 2d-array

ex)

input : 5

output

     1

    1 1

   1 2 1

 1 3  3 1

1 4 6 4  1

 

n번째의 m은 n-1의 m-1+m 의 값을 가져옴

 

time complexity : O(n^2)

space comlexity : O(n*m)

 

rust solution

impl Solution {
    pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
        if num_rows == 1 { return vec![vec![1]]; }

        let mut ret_val: Vec<Vec<i32>> = vec![];

        for i in 0..num_rows {
            let mut cur_arr: Vec<i32> = vec![1; (i+1) as usize];
            ret_val.push(cur_arr);
            if i == 0 || i == 1 { continue; }

            for j in 0..ret_val[i as usize].len() as i32 {
                if j == 0 || j == (ret_val[i as usize].len() - 1) as i32 { continue; }
                ret_val[i as usize][j as usize] = ret_val[(i - 1) as usize][(j - 1) as usize] + ret_val[(i - 1) as usize][j as usize];
            }
        }
        ret_val
    }
}