# 演算法導論 HW11
https://hackmd.io/@wang1234/BJE7IYmDc
## 第1題: shortest path in multi-stage graph
<font color="DarkGray" class="small">下圖為一個multi-stage graph，請分別以forward approach與backward approach，推導出點1到12的最短路徑。</font>
最短路徑:
1 → 2 → 7 → 10 → 12
1 → 3 → 6 → 10 → 12

## 第2題: 計算正方形數量
[1277. Count Square Submatrices with All Ones](https://leetcode.com/problems/count-square-submatrices-with-all-ones/)
<font color="Black">解題思路:
> 
(大概知道是這樣的概念,但還無法自行寫出此概念的全部程式碼)</font>

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n+1) for _ in range(m+1)]
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j]:
                    dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1
                    ans += dp[i+1][j+1]
        return ans

花60分鐘，抄:
[Understandable Python3 DP with Explanation](https://leetcode.com/problems/count-square-submatrices-with-all-ones/solutions/3498069/understandable-python3-dp-with-explanation/)
[DP with figure explanation](https://leetcode.com/problems/count-square-submatrices-with-all-ones/solutions/441620/dp-with-figure-explanation/)
[Easy to understand](https://leetcode.com/problems/count-square-submatrices-with-all-ones/solutions/2725029/easy-to-understand/)

## 第3題: 所有可能的合法成對括號
[22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)
<font color="Black">解題思路:
> 括號的組成方式可以從數量少一個的組成方式裡推演出來
所以我建了一個名為dp的雙層list,dp[0]的裡存放的就是一個括號的組成方式["()"],
當想要查的數量m還沒推導過,dp[m-1]為空列表時,就依上圖的方法去推導,並用轉換set與list的方式去除重複的結果</font>

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp=[ [] for _ in range(n)]
        dp[0]=["()"]
        def generate(m):
            if dp[m-1]!=[]:
                return dp[m-1]
            else:
                temp=set()
                generate(m-1)
                for i in dp[m-1-1]:
                    for j in range(len(i)):
                        temp.add(i[:j]+"()"+i[j:])
                dp[m-1]=list(temp)
                return dp[m-1]
        generate(n)
        return dp[n-1]

花70分鐘，參考:
[python code using dp](https://leetcode.com/problems/generate-parentheses/solutions/3152520/python-code-using-dp/)

## 第4題: 巴士卡三角形
[118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)
<font color="Black">解題思路:
> 
ans為雙層list,存放整個三角形,temp則為每一列編輯時使用,
在for迴圈中往temp內新增元素,例如:在第0圈新增一個1,到第1圈再加入一個1,變成[1,1] ,然後在每圈迴圈的最後把temp新增到ans裡,
但是到第2圈,要編輯ans[2]時,因為ans[2][1]的值,是ans[1][0]和ans[1][1]的和,
所以for迴圈第2圈開始,temp的編輯需要用到上一圈加進ans的內容來計算</font>

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans=[]
        temp=[]
        for i in range(numRows):
            if i>=2:
                for j in range(len(temp)):
                    if j>=1:
                        temp[j]=ans[-1][j-1]+ans[-1][j]
            temp.append(1)
            ans.append(list(temp))
        return ans

花40分鐘，完全靠自己

## 第4題: 存積雨水
[392. Is Subsequence](https://leetcode.com/problems/is-subsequence/)
<font color="Black">解題思路:
> 在每次的函式呼叫中傳入子序列s和目標序列t,
抓子序列的第一個字元s[0],用find函式在t中尋找,
當在t中找不到時(返回值=-1),return False;
當有找到時,返回值為s在t中的位置索引值x,將s扣除已找到的第一位以及t在索引值x後面的剩餘字串傳入遞迴,
直到參數s接收到的是空字串,表示原本子序列裡的字元都已依序在目標序列中找到,so return True</font>

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if s=='':
            return True
        x=t.find(s[0])
        if x==-1:
            return False
        else:
            return self.isSubsequence(s[1:],t[x+1:])


花30分鐘，求助:
[python 遞迴呼叫返回None的問題及解決方法_程式設計_程式人生](https://www.796t.com/article.php?id=16458)

## 心得
最後兩題雖然有寫出能pass的程式碼，但自己都有點疑惑是否是用到了dynamic programming的概念