# **演算法作業 HW11**
<font size=5>**1. shortest path in multi-stage graph**</font>
---
* 下圖為一個multi-stage graph，請分別以forward approach與backward approach，推導出點1到12的最短路徑。
Ans：16

**forward approach：**


**backward approach**:


<font size=6>**Dynamic Programming**</font>
---
<font size=5>**2. 計算正方形數量**</font>
---
[1277. Count Square Submatrices with All Ones - LeetCode](https://leetcode.com/problems/count-square-submatrices-with-all-ones/)
將邊長n正方形的結構拆成3個邊長正方形加上右下角一點。
右下角的點能擴張成多大的正方形則取決於另外三個正方形中最小的一個。
像下圖示意的一樣：
參考網上答案，完成時間：20分鐘。

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        /*
        這邊先以dp代指matrix
        假設dp[i][j]=n
        dp[i][j]可當作最大邊長為n的正方形的右下角
        同時也代表包含此點的正方形有n個
        而dp[i][j]只能從dp[i-1][j-1],dp[i-1][j],dp[i][j-1]中的最小值擴張
        不然會有缺口，無法構成正方形
        (EX:3個邊長n-1的正方形加上右下角一點才能構成邊長n的正方形)
        因此推得dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
        */
        int res=0;
        for(int i=0;i<matrix.size();++i)
            for(int j=0;j<matrix[0].size();++j)
            {
                if(matrix[i][j] && i && j)
                    matrix[i][j] += 
                    min({matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1]});
                res += matrix[i][j];
            } 
        return res;
    }
};


<font size=5>**3. 所有可能的合法成對括號**</font>
---
[22. Generate Parentheses - LeetCode](https://leetcode.com/problems/generate-parentheses/)
題目要求所有可能的排列。
在dfs裡加上括號的條件往下探訪所有可能路徑就好。
完全靠自己，完成時間：五分鐘。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string>res;
        string path;
        //往下探訪全部路徑
        dfs(res,path,n,n);
        return res;
    }
    void dfs(vector<string>&v,string path,int l,int r)
    {
        if(l==0 && r==0)
        {
            v.push_back(path);
            return;
        }
        if(l)//還有左括號就先丟
        {
            string s=path+"(";
            dfs(v,s,l-1,r);
        }
        if(r>l)//剩下右括號比左括號多(這樣丟進去才可以配對)
        {
            string s=path+")";
            dfs(v,s,l,r-1);
        }
    }
};


<font size=5>**4. 巴士卡三角形**</font>
---
[118. Pascal’s Triangle - LeetCode](https://leetcode.com/problems/pascals-triangle/)
計算每一層後再推下一層，沒什麼好說的。
完全靠自己，完成時間：一分鐘。

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


<font size=5>**5. Is Subsequence**</font>
---
[392. Is Subsequence - LeetCode](https://leetcode.com/problems/is-subsequence/)
用兩個指標去遍歷字串和子字串。
字元相同才繼續推進。
若到最後子字串被成功推完，則代表子字串可以從字串裡擷取出。
完全靠自己，完成時間：一分鐘。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int si=0,ti=0;
        for(;ti<t.length();++ti)
            if(t[ti]==s[si])
                ++si;
        if(si==s.length())
            return true;
        else
            return false;
    }
};


<font size=5>**6. 本周心得**</font>
---
dp這類的題型果然很難當下推出來。

---
若有錯誤歡迎指正