演算法作業12

第1題: shortest path in multi-stage graph

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

forward approach

d(1,12)

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

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)\}$

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)\}$

d(9,12)

$d(9,12)=4$

d(10,12)

$d(10,12)=2$

d(11,12)

$d(11,12)=4$

推回去

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$

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$

最短路徑 d(1,12)=16

$d(1,12)=min\{9+7,7+9,3+20,2+16\}=16$

backward approach

d(1,12)

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

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)\}$

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)\}$

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$

推回去

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$

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$

最短路徑 d(1,12)=16

$d(1,12)=min\{4+15,2+14,6+16\}=16$

第2題: leetcode70延伸

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

過程

結果

程式碼

#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求解

過程

結果

第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分鐘

完成程度

完全自己解出

心得

已填