# 演算法作業12

## 第1題: shortest path in multi-stage graph

- 下圖為一個multi-stage graph，請分別以forward approach與backward approach，推導出點1到12的最短路徑。


### forward approach

:::success
#### d(1,12)
$d(1,12)=min\{9+d(2,12),7+d(3,12),3+d(4,12),2+d(5,12)\}$
:::

:::success
#### d(2,12)
$d(2,12)=min\{4+d(6,12),2+d(7,12),1+d(8,12)\}$

#### d(3,12)
$d(3,12)=min\{2+d(6,12),7+d(7,12)\}$

#### d(4,12)
$d(4,12)=min\{11+d(8,12)\}$

#### d(5,12)
$d(5,12)=min\{11+d(7,12),8+d(8,12)\}$
:::

:::success
#### d(6,12)
$d(6,12)=min\{6+d(9,12),5+d(10,12)\}$

#### d(7,12)
$d(7,12)=min\{4+d(9,12),3+d(10,12)\}$

#### d(8,12)
$d(8,12)=min\{5+d(10,12),6+d(11,12)\}$
:::

:::success
#### d(9,12)
$d(9,12)=4$

#### d(10,12)
$d(10,12)=2$

#### d(11,12)
$d(11,12)=4$
:::

推回去

:::success
#### d(6,12)
$d(6,12)=min\{6+4,5+2\}=7$

#### d(7,12)
$d(7,12)=min\{4+4,3+2\}=5$

#### d(8,12)
$d(8,12)=min\{5+4,6+4\}=9$
:::

:::success
#### d(2,12)
$d(2,12)=min\{4+7,2+5,1+9\}=7$

#### d(3,12)
$d(3,12)=min\{2+7,7+5\}=9$

#### d(4,12)
$d(4,12)=min\{11+9\}=20$

#### d(5,12)
$d(5,12)=min\{11+5,8+9\}=16$
:::

:::success
### 最短路徑 d(1,12)=16
$d(1,12)=min\{9+7,7+9,3+20,2+16\}=16$
:::

### backward approach

:::success
#### d(1,12)
$d(1,12)=min\{4+d(1,9),2+d(1,10),6+d(1,11)\}$
:::

:::success
#### d(1,9)
$d(1,9)=min\{6+d(1,6),4+d(1,7)\}$

#### d(1,10)
$d(1,10)=min\{5+d(1,6),3+d(1,7),5+d(1,8)\}$

#### d(1,11)
$d(1,11)=min\{6+d(1,8)\}$
:::

:::success
#### d(1,6)
$d(1,6)=min\{4+d(1,2),2+d(1,3)\}$

#### d(1,7)
$d(1,7)=min\{2+d(1,2),7+d(1,3),11+d(1,5)\}$

#### d(1,8)
$d(1,8)=min\{1+d(1,2),11+d(1,4),8+d(1,5)\}$
:::

:::success
#### d(1,2)
$d(1,2)=9$

#### d(1,3)
$d(1,3)=7$

#### d(1,4)
$d(1,4)=3$

#### d(1,5)
$d(1,5)=2$
:::

推回去

:::success
#### d(1,6)
$d(1,6)=min\{4+9,2+7\}=9$

#### d(1,7)
$d(1,7)=min\{2+9,7+7,11+2\}=11$

#### d(1,8)
$d(1,8)=min\{1+9,11+3,8+2\}=10$
:::

:::success
#### d(1,9)
$d(1,9)=min\{6+9,4+11\}=15$

#### d(1,10)
$d(1,10)=min\{5+9,3+11,5+10\}=14$

#### d(1,11)
$d(1,11)=min\{6+10\}=16$
:::

:::success
### 最短路徑 d(1,12)=16
$d(1,12)=min\{4+15,2+14,6+16\}=16$
:::

## 第2題: leetcode70延伸

- 要上爬上10階的梯子，每一步可爬1階，2階，或3階，請問總共有幾種走法。
- 請仿照影片使用dp求解。

:::success
### 過程


### 結果

### 程式碼

#include <bits/stdc++.h>
using namespace std;

int f(int n)
{
    int dp[n+1]={1,1,2};
    for(int i=3;i<=n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
    }
    return dp[n];
}

int main()
{
    int n;
    cin>>n;
    cout<<f(n);
}

:::

## 第3題: Leetcode 1395應用

- 一個數列[4,2,5,3,6,1]，從其中挑出三個數，三數須要為遞增或遞減，請問有幾種挑選法？
- 請仿照影片使用dp求解

:::success
### 過程


### 結果


:::

## 第4題: 計算正方形數量

### 解題思路

我是大笨蛋，我卡超久，
主要是推DP的轉移的時間，
簡單來說，就是取上、右的最小值然後+1，再存起來
如果這格是0就無視它

### 程式碼

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int i,j,ans=0,mi;
        for(i=0;i<matrix.size();i++)
        {
            for(j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j])
                {
                    mi=100000;
                    if(i)
                    {
                        mi=min(mi,matrix[i-1][j]);
                    }
                    if(j)
                    {
                        mi=min(mi,matrix[i][j-1]);
                    }
                    if(i&&j)
                    {
                        mi=min(mi,matrix[i-1][j-1]);
                        matrix[i][j]=mi+1;
                    }
                    ans+=matrix[i][j];
                }
            }
        }
        return ans;
    }
};

### 測試輸出輸入的畫面截圖


### 花費時間

27分鐘

### 完成程度

完全自己解出

## 第5題: 所有可能的合法成對括號

### 解題思路

我這樣算開外掛嗎
next_permutation可以把所有排序取出來
只要判斷是不是正確的就好

### 程式碼

class Solution {
public:
    bool f(string s)
    {
        int i,k=0;
        for(i=0;i<s.size();i++)
        {
            if(s[i]=='(')
            {
                k++;
            }
            else
            {
                if(k<=0)
                {
                    return 0;
                }
                k--;
            }
        }
        return k==0;
    }

    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string s;
        int i;
        for(i=0;i<n;i++)
        {
            s+='(';
        }
        for(i=0;i<n;i++)
        {
            s+=')';
        }
        do
        {
            if(f(s))
            {
                ans.push_back(s);
            }
        }
        while(next_permutation(s.begin(),s.end()));
        return ans;
    }
};

### 測試輸出輸入的畫面截圖

### 花費時間

14分鐘

### 完成程度

完全自己解出

## 第6題: 巴士卡三角形

### 解題思路

初始是`1`
一直做
挖上面的`ans`來產生下面的`tmp`
前後再補1
存到ans
直到numRows

### 程式碼

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

### 測試輸出輸入的畫面截圖


### 花費時間

6分鐘

### 完成程度

完全自己解出

## 心得

已填