iT邦幫忙

2

動態規劃經典題: 帕斯卡三角形

哈囉,今天跟大家介紹一個蠻有用的概念,
叫做「帕斯卡三角形」,
規則除了兩側的1之外,
三角形的每個數都等於上方兩個數字相加,如圖示:

https://ithelp.ithome.com.tw/upload/images/20200502/20117114wIOZxO55fN.png

「帕斯卡三角形」在數學上相當有用,
譬如說排列組合的組合數C(n, k)就是「帕斯卡三角形」第n列第k個數(從0開始數)

多項式(1+x)^n的展開式的係數也正好是帕斯卡三角形的第n列,譬如:

(1+x)^1 = 1+x  (係數: 1,1)
(1+x)^2 = 1+2x+x^2  (係數: 1,2,1)
(1+x)^3 = 1+3x+3x^2+x^3  (係數: 1,3,3,1)

來學習如何以程式生出「帕斯卡三角形」。
公式: C[i][j]=C[i-1][j-1]+C[i-1][j]

一、生出整個帕斯卡三角形

參考題目: LeetCode- 118. Pascal's Triangle
給你一個非負整數n,生出n列的「帕斯卡三角形」。
<c++>:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> pas(numRows);
        for(int i=0; i<pas.size(); i++){
            pas[i] = vector<int>(i+1, 1);
        }
        for(int i=2; i<pas.size(); i++){
            for(int j=1; j<i;j++){
                pas[i][j]=pas[i-1][j-1]+pas[i-1][j];
            }
        }
        return pas;
    }
};

python程式也很簡單就順便打一打:

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        pas = [[1]*(i+1) for i in range(numRows)]
        for i in range(2,numRows):
            for j in range(1,i):
                pas[i][j]=pas[i-1][j-1]+pas[i-1][j]
        return pas

二、僅生出某一列帕斯卡三角形

參考題目: LeetCode- 119. Pascal's Triangle II
給你一個非負整數n,生出第n列的「帕斯卡三角形」,
譬如n=3時,回傳[1,3,3,1]

解法一: 空間複雜度O(n^2)

本題其實是第一題的子題,程式直接拿來套用就會過關了

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> pas(rowIndex+1);
        for(int i=0; i<pas.size(); i++){
            pas[i] = vector<int>(i+1, 1);
        }
        for(int i=2; i<pas.size(); i++){
            for(int j=1; j<i;j++){
                pas[i][j]=pas[i-1][j-1]+pas[i-1][j];
            }
        }
        return pas[pas.size()-1];
    }
};

解法二: 空間複雜度O(n)

但既然我們只要回傳最後一列帕斯卡三角形,
如果開n列陣列來記錄完整的帕斯卡三角形,
便顯的有點浪費空間,
省空間的方法如下:

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> pas(rowIndex+1, 1);
        for(int i=2; i<pas.size(); i++){
            for(int j=i-1; j>0;j--){
                pas[j]+=pas[j-1];
            }
        }
        return pas;
    }
};

說明: 例如n=4,

一開始初始值pas=[1,1,1,1,1],
i=2 迭代後 => pas=[1,2,1,1,1]
i=3 迭代後 => pas=[1,3,3,1,1]
i=4 迭代後 => pas=[1,4,6,4,1]
大家實際在腦中跑跑看經過迴圈後會發生什麼事大概就會懂。

尚未有邦友留言

立即登入留言