---
# System prepended metadata

title: algo w13
tags: [Algorithm]

---

# 演算法第13周
## 觀念題
### 第1題: shortest path in multi-stage graph
- forward approach
    ![image](https://hackmd.io/_uploads/H1gCkGPV0.png)
    :::spoiler python
    ```python=
    INF = float('inf')

    node, edge = [int(x) for x in input().split()]
    graph = [[INF for _ in range(node)] for _ in range(node)]

    for i in range(edge):
        u, v, w = [int(x) for x in input().split()]
        graph[u-1][v-1] = w
    for row in graph:
        for elem in row:
            print(elem, end='\t')
        print()

    def shortestPath(graph):
        node = len(graph)
        dist = [0] * node
        for i in range(1,node):
            dist[i] = INF
            for j in range(node):
                if graph[j][i] != INF:
                    dist[i] = min(dist[i], graph[j][i] + dist[j])
        return dist[node-1]

    print(shortestPath(graph))
    ```
    :::
    - 過程
        ![](https://raw.githubusercontent.com/kevin0920911/algorGIF/main/week13/question1_forward.gif)
- backward approach
    ![image](https://hackmd.io/_uploads/Hk6CyzvEA.png)
    :::spoiler Python
    ```python=
    INF = float('inf')

    node, edge = [int(x) for x in input().split()]
    graph = [[INF for _ in range(node)] for _ in range(node)]

    for i in range(edge):
        u, v, w = [int(x) for x in input().split()]
        graph[u-1][v-1] = w

    def shortestPath(graph):
        node = len(graph)
        dist = [0] * node
        for i in range(node-2,-1,-1):
            dist[i] = INF
            for j in range(node):
                if graph[i][j] != INF:
                    dist[i] = min(dist[i], graph[i][j] + dist[j])
        return dist[0]

    print(shortestPath(graph))
    ```
    :::
    - 過程
        ![](https://raw.githubusercontent.com/kevin0920911/algorGIF/main/week13/question1_back.gif)
> 答案: 16
> 路徑: 1 -> 3 -> 6 -> 10 -> 12
### 第2題: leetcode70延伸
:::info
**前情提要**
[leetcode 70](https://leetcode.com/problems/climbing-stairs/)
- 阿就費式數列阿
    :::spoiler C++
    ```C++=
    class Solution {
    public:
        int climbStairs(int n) {
            vector<int> dp(n+1,0);
            dp[0] = 1;
            dp[1] = 1;

            for (int i=2;i<=n;i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
    };
    ```
    :::
:::
- 程式碼
    ~~我可以只交程式碼嗎~~
    :::spoiler Python
    ```python=
    n = int(input('多少階梯? '))

    dp = [0] * (n+1)

    dp[0] = 1
    dp[1] = 1
    dp[2] = 2

    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

    print(f"Step: {dp[n]}")
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/BkJSX3L4C.png)
- 過程說明
    - 首先，把轉移式列出來
        - $dp[i]=dp[i-1]+dp[i-2]+dp[i-3]$
    - 然後列出起始條件
        - $dp[0] = 1$ -> 爬上0個階層也是一種方法
        - $dp[1] = 1$
        - $dp[2] = 2$ -> (1,1) and (2)
    - 最終解
        - $dp[n]$
    - 過程 
        ![image](https://raw.githubusercontent.com/kevin0920911/algorGIF/main/week13/qustion2.gif)
> 答案: 274
### 第3題: Leetcode 1395應用
[leetcode 1395](https://leetcode.com/problems/count-number-of-teams/)
- 解法一: 2D DP
    - 程式碼
        ~~我可以只交程式碼嗎畫圖好累，殺了我~~
        :::spoiler C++
        ```C++=
        class Solution {
        public:
            int numTeams(vector<int>& rating) {
                int n = rating.size();

                vector<vector<int>> inc_dp(4,vector<int>(n,0));
                vector<vector<int>> dec_dp(4,vector<int>(n,0));

                for (int i=0; i<n; i++){
                    inc_dp[1][i] = 1;
                    dec_dp[1][i] = 1;
                }

                for (int i=2; i<4; i++){
                    for (int j=0; j<n; j++){
                        for (int k=0; k<j; k++){
                            if (rating[j] > rating[k])
                                inc_dp[i][j] += inc_dp[i-1][k];
                            else
                                dec_dp[i][j] += dec_dp[i-1][k];
                        }
                    }
                }

                int sum = 0;
                for_each(inc_dp[3].begin(),inc_dp[3].end(), [&](const auto & i){sum+=i;});
                for_each(dec_dp[3].begin(),dec_dp[3].end(), [&](const auto & i){sum+=i;});

                return sum;
            }
        };
        ```
        :::
    - 執行結果
        ![image](https://hackmd.io/_uploads/HyBOYAL4A.png)
    - 執行過程
        - 首先先理解幾點
            1. $dp[i][j]$含意: $i$代表著連續遞增or遞減幾個數字，$j$代表一定有第$j$個數字
            2. 因此我們可以用過去連續次數連加上現在新加入的元素，也就是假如一個數列$[1,2,3,4]$
                - 有兩個數列遞增的可能是
                    - (1 , 2), (2 , 3), (1,3)
                - 那如果是這樣，新加入的數字4是不是直接跟最大的比較就好了
                    - (1,2,4), (2,3,4), (1,3,4)
            3. 注意一下其實我這邊分成兩個表，一個是遞增dp，一個是遞減dp，但因為邏輯差不多，所以看起來類似
        - 可以做轉移式了(這邊以遞增表作舉例，遞減表反之)
            - $dp[i][j] = sum(dp[i-1][x])\space \forall x\in[0,j) \space\space\space\space if \space\space\space\space arr[j] < arr[x]$
        - 初始條件
            - $dp[i] = [1]*n$
        - 最終解
            - $\Sigma dp[3][i]$
        - 過程
            ![](https://raw.githubusercontent.com/kevin0920911/algorGIF/main/week13/question3.gif)
- 解法二: 1D DP
    - 就是老師的作法
    - 程式碼
        :::spoiler Python
        ```Python=
        class Solution:
        def numTeams(self, rating: List[int]) -> int:
            n = len(rating)

            smallerDP = [0 for _ in range(n)]
            lagerDP   = [0 for _ in range(n)]
            count = 0

            for i in range(n):
                for j in range(i):
                    if rating[j] < rating[i]:
                        count += smallerDP[j]
                        smallerDP[i] += 1
                    else:
                        count += lagerDP[j]
                        lagerDP[i] += 1
            return count
        ```
        :::
    - 執行結果
        ![image](https://hackmd.io/_uploads/HyzcZfdEA.png)
    - 執行過程
        - 其實就是解法一優化過程
        - 如果觀察一下剛剛的數列可以看到一件事，`inc_dp[1]` 與 `dec_dp[1]`其實就是找有幾個數字比他小or大，所以我們已經有足夠的線索拼出轉移式了(這邊以larger做舉例)
            - $lagerDP[i]=num(arr[i]>arr[j]) \forall i>j$
            - 然後假如成立我們還可以順便算出加入這個數組時有多少可能
            - 只能說，想到這個的太電了:place_of_worship::place_of_worship::place_of_worship::place_of_worship::place_of_worship::place_of_worship::place_of_worship::place_of_worship::place_of_worship: 
    - 過程
        ![](https://raw.githubusercontent.com/kevin0920911/algorGIF/main/week13/q3.gif)
> 答案: 6
## 實作題
### 第4題: 計算正方形數量
[leetcode 1277](https://leetcode.com/problems/count-square-submatrices-with-all-ones/)
- 程式碼
    :::spoiler C++
    ```C++=
    // fast IO
    static auto __ = []()
    {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        return 0;
    }();
    class Solution {
    public:
        int countSquares(vector<vector<int>>& matrix) {
            int row   = matrix.size();
            int col   = matrix[0].size();
            int count = 0;
            for (int i=0;i<row;i++){
                for (int j=0;j<col;j++){
                    if (i!=0 && j!=0 && matrix[i][j] != 0)
                        matrix[i][j] += min({matrix[i-1][j],matrix[i][j-1],matrix[i-1][j-1]});
                    count+=matrix[i][j];
                }
            }
            return count;
        }
    };
    ```
    :::
- 執行結果
    ![image](https://hackmd.io/_uploads/BJPhxMvVR.png)
- 花費時間: 體感1.5小時
- 完成程度: 有參考別人
    - [ref](https://leetcode.com/problems/count-square-submatrices-with-all-ones/solutions/2363854/3-solutions-recursion-memoization-tabulation-easy-to-understand/)
- 思路
    - 首先呢，我們可以先定義$dp[i][j]$為從(i,j)到(0,0)有多少長方形
    - 那如果這邊是1代表，可以在擴展長方形
        - 如果可以擴展，那哪三處可以擴展
            - 上面，左邊，斜上方
        - 代表`dp[i][j] += min(up,left,upper left)`
    - 所以，轉移式來囉
        - $dp[i][j]+= min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) \space \space\space if \space\space\space dp[i][j]=1$
    - 答案是將全部總和
### 第5題: 所有可能的合法成對括號
[leetcode 22](https://leetcode.com/problems/generate-parentheses/)
- 程式碼
    - 作法一: DFS 
        - 程式碼
            :::spoiler C++ 
            ```C++=
            // fast IO
            static auto __ = []()
            {
                std::ios_base::sync_with_stdio(false);
                std::cin.tie(nullptr);
                std::cout.tie(nullptr);
                return 0;
            }();
            class Solution {
            public:
                vector<string> generateParenthesis(int n) {
                    int LP=0, RP=0;
                    vector<string> ans;
                    function<void(int, int, string)> slove = [&](int LP,int RP, string s){
                        if (s.size() == 2*n){
                            ans.push_back(s);
                            return;
                        } 

                        if (LP<n) slove(LP+1,RP,s+'(');
                        if (LP>RP) slove(LP,RP+1,s+')');
                    };
                    slove(LP,RP,"");
                    return ans;
                }
            };
            ```
            :::
        - 執行結果
            ![image](https://hackmd.io/_uploads/BkPHZGDER.png)
        - 花費時間: 30分鐘
        - 完成程度: 有參考別人
            - [ref](https://www.cnblogs.com/grandyang/p/4444160.html)
        - 思路
            - 這題用回朔法概念解
            - 所以呢我們就先加入左括號
            - 如果當前的狀態左括號比較多，那就加入右括號
            - 然後假如當前字符長度已經達到2*n，就可以當成答案了
    - 作法二: DP
        - ~~90%是被王老闆跟張紹維嘴用遞迴，然後賭氣寫DP~~，結果根本通靈不了，我願稱其是大通靈程式設計
        - 程式碼
            :::spoiler C++
            ```C++=
            // fast IO
            static auto __ = []()
            {
                std::ios_base::sync_with_stdio(false);
                std::cin.tie(nullptr);
                std::cout.tie(nullptr);
                return 0;
            }();
            class Solution {
            public:
                vector<string> generateParenthesis(int n) {
                    unordered_map<int, unordered_set<string> > ans;
                    ans[1] = {"()"};
                    for (int i=2; i<=n; i++){
                        unordered_set<string> tmp;

                        // ADD s[i-j] and s[j] 
                        for (int j=1; j<i; j++){
                            for (const auto &s1: ans[i-j]){
                                for (const auto &s2: ans[j]){
                                    tmp.insert(s1+s2);
                                }
                            }
                        }

                        // ADD (+s[i-1]+)
                        for (const auto &s: ans[i-1]){
                            tmp.insert("("+s+")");
                        }

                        // push in dp array
                        ans[i] = tmp;
                    }

                    return vector<string>(ans[n].begin(),ans[n].end());
                }
            };
            ```
            :::
        - 執行結果
            ![image](https://hackmd.io/_uploads/SklzWfwNC.png)
        - 花費時間: 體感2小時:derelict_house_building: 
        - 完成程度: 參考別人的程式碼
            - [ref 1](https://leetcode.com/problems/generate-parentheses/solutions/2610178/22-generate-parentheses/)
        - 思路
            - 首先，可以這樣思考
                - 上一個狀態只要前後加上括號就是其中一解
                - 枚舉全部可能，可以使$a+b=i$，只要字串接合就是答案
            - 所以有了這些我們可以做成轉移式了
                - $dp[i] = '(' + dp[i-1] + ')'$
                - $dp[i] = dp[a] + dp[b]$  $\forall a+b=i$
            - 接下來初始狀態就很簡單了
                - $dp[1] = "()"$
### 第6題: 巴士卡三角形
[leetcode 118](https://leetcode.com/problems/pascals-triangle/description/)
- 解法
    - ~~為什麼這邊改用Rust呢，因為解法二用Racket就有兩個R了~~
    - 做法一: 使用GIF的作法
        - 程式碼
            :::spoiler Rust
            ```rust=
            impl Solution {
                pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
                    let mut dp: Vec<Vec<i32>> = Vec::with_capacity(num_rows as usize);

                    for i in 0..num_rows as usize{
                        let mut row:Vec<i32> = vec![1; i+1];

                        for j in 1..i{
                            row[j] = dp[i-1][j-1] + dp[i-1][j];
                        }
                        dp.push(row);
                    }

                    dp
                }
            }
            ```
            :::
        - 執行結果
            ![image](https://hackmd.io/_uploads/BJY5ZfDNA.png)
        - 花費時間: 30分鐘
        - 完成程度: 靠自己(還是要說leetcode題目已經把解法寫出來了...)
        - 思路
            - ~~題目都給圖了笑死~~
            - ![](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)
            - 好反正就是轉移式
                - $dp[i][j] = dp[i-1][j-1]+dp[i-1][j]$
    - 做法二: 使用數學的方法
        - ~~其實只是想寫寫看類LISP語言~~
        - 程式碼
            :::spoiler Racket
            ```racket=
            (require math/number-theory)

            (define/contract (generate numRows) (-> exact-integer? (listof (listof exact-integer?)))
                (map  
                    ( lambda (i)  
                        (map (curry binomial i) (range (+ 1 i)))
                    )
                    (range numRows)
                )
            )
            ```
            :::
        - 執行結果
            ![image](https://hackmd.io/_uploads/rJOobMwE0.png)
        - 花費時間: 1小時
            - ~~我就不該寫這種神經病語言~~
        - 完成程度: 有參考他人的程式碼
            - ~~其實就是我根本不會LISP~~
            - [ref](https://leetcode.com/problems/pascals-triangle/solutions/3031455/simple-racket-solution/)
        - 思路
            - 好反正就是數學的問題，跟DP沒關西
            - ![image](https://hackmd.io/_uploads/r1ZypfwEA.png)

## 心得
今天學了DP，寫完那題爬樓梯才想到大一的程式設計考手寫扣，題目是費氏數列，然後我開陣列寫，被老師說我偷吃步她還沒教array:(，原來那時候被我稱為開陣列的方式就是動態規劃。

這周的作業我深刻體會到了DP靠通靈，難怪系程式第一名的陳同學和張同學都說，DP靠通靈，只能說不要在外面說你會DP，因為可能通靈不出來;(。

雖然說前面一直在diss DP，但老實說，DP這個解法確實會幫你省很多時間，我平常用遞迴的問題換成DP效率確實有高上許多，他真是讓人又愛又恨^^。