# Week 15 - 作業講解
Benson Chiu @ Sprout Taipei 2022

---
## Problem #140 円円送禮物
### 解題思路
- 觀察：第 $n$ 步的走法都可以從第 $n-1$ 步推得
- 限制條件：
- 藍藍不相鄰，綠綠不相鄰
- 頭尾不能一藍一綠

----
### 也就是說
- 在推導第 $n$ 步的方法數時，我們不但要知道第 $n-1$ 步的方法數是多少
- 還要知道前一步的顏色（避免兩個顏色相鄰）
- 也要知道來自第一步是某個顏色的方法數是多少（方便在最後的時候判斷頭尾不能一藍一綠的限制條件）
---
### 遞迴關係式
假設 $0$ 代表紅色，$1$ 代表綠色，$2$ 代表藍色。

$f(n,a,b)$代表：(1) 第 $n$ 格為顏色 $a$ 且 (2) 首格為顏色 $b$ 的方法數

#### 初始條件
$$ f(1,0,0) = f(1, 1, 1) = f(1,2,2) =1 $$
其餘 $n = 1$ 的函數值皆為 $0$

#### 遞迴關係
##### 第 $n$ 格為紅色
$$\begin{cases} f(n,0,0) = f(n-1,0,0) + f(n-1,1,0) + f(n-1,2,0) \\ f(n,0,1) = f(n-1,0,1) + f(n-1,1,1) + f(n-1,2,1) \\ f(n,0,2) = f(n-1,0,2) + f(n-1,1,2) + f(n-1,2,2)\end{cases}$$

##### 第 $n$ 格為綠色
$$\begin{cases} f(n,1,0) = f(n-1,0,0) + f(n-1,1,0) \\ f(n,1,1) = f(n-1,0,1) + f(n-1,1,1) \\ f(n,1,2) = f(n-1,0,2) + f(n-1,1,2) \end{cases}$$

##### 第 $n$ 格為藍色
$$\begin{cases} f(n,2,0) = f(n-1,0,0) + f(n-1,2,0) \\ f(n,2,1) = f(n-1,0,1) + f(n-1,2,1) \\ f(n,2,2) = f(n-1,0,2) + f(n-1,2,2) \end{cases}$$

### 結束條件（假設所求為塗 $N$ 格的方法數）
==頭尾不能一藍一綠!!==
$$f(N) = f(N,0,0) + f(N,0,1) + f(N,0,2) \text{ (Red)}\\ + f(N,1,0) + f(N,1,1) \text{ (Green)}\\+f(N,2,0) + f(N,2,2) \text{ (Blue)}$$

---
### 想用遞迴嗎？
- $N < 10^5$ ，可想而知遞迴樹有多龐大，準備吃 TLE 吧！:poop:
- 解題小技巧：看到結果要除以 $MOD$ (此處為 $1000007$)的餘數，想到 DP !
- 在輸入測試資料前，我們就預先把表格建立好，之後每一次輸入詢問就直接存取！
---
### 建表

   int dp[100001][3][3] = {0};

    dp[1][0][0] = 1;
    dp[1][1][1] = 1;
    dp[1][2][2] = 1;        
    for(int i = 2; i <= 1e5; i++)
    {
        dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0]) % MOD; 
        dp[i][0][1] = (dp[i-1][0][1] + dp[i-1][1][1] + dp[i-1][2][1]) % MOD; 
        dp[i][0][2] = (dp[i-1][0][2] + dp[i-1][1][2] + dp[i-1][2][2]) % MOD; 

        dp[i][1][0] = (dp[i-1][0][0] + dp[i-1][1][0]) % MOD; 
        dp[i][1][1] = (dp[i-1][0][1] + dp[i-1][1][1]) % MOD; 
        dp[i][1][2] = (dp[i-1][0][2] + dp[i-1][1][2]) % MOD; 

        dp[i][2][0] = (dp[i-1][0][0] + dp[i-1][2][0]) % MOD; 
        dp[i][2][1] = (dp[i-1][0][1] + dp[i-1][2][1]) % MOD; 
        dp[i][2][2] = (dp[i-1][0][2] + dp[i-1][2][2]) % MOD; 
    }        

---
### 取值

    int t = 0;
    cin >> t;
    for(int k = 0; k < t; k++)
    {
        int n;
        cin >> n;
        int ans = (dp[n][0][0] + dp[n][0][1] + dp[n][0][2] + dp[n][1][0] + dp[n][1][1] + dp[n][2][0]  + dp[n][2][2]) % MOD;
        cout << ans << endl;
    }

---
### 完整程式碼

#include<iostream>
using namespace std;
#define MOD (1000007)

int main()
{
    int dp[100001][3][3] = {0};

    dp[1][0][0] = 1;
    dp[1][1][1] = 1;
    dp[1][2][2] = 1;        
    for(int i = 2 i <= 1e5; i++)
    {
        dp[i][0][0] = (dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0]) % MOD; 
        dp[i][0][1] = (dp[i-1][0][1] + dp[i-1][1][1] + dp[i-1][2][1]) % MOD; 
        dp[i][0][2] = (dp[i-1][0][2] + dp[i-1][1][2] + dp[i-1][2][2]) % MOD; 

        dp[i][1][0] = (dp[i-1][0][0] + dp[i-1][1][0]) % MOD; 
        dp[i][1][1] = (dp[i-1][0][1] + dp[i-1][1][1]) % MOD; 
        dp[i][1][2] = (dp[i-1][0][2] + dp[i-1][1][2]) % MOD; 

        dp[i][2][0] = (dp[i-1][0][0] + dp[i-1][2][0]) % MOD; 
        dp[i][2][1] = (dp[i-1][0][1] + dp[i-1][2][1]) % MOD; 
        dp[i][2][2] = (dp[i-1][0][2] + dp[i-1][2][2]) % MOD; 
    }        

    int t = 0;
    cin >> t;
    for(int k = 0; k < t; k++)
    {
        int n;
        cin >> n;
        int ans = (dp[n][0][0] + dp[n][0][1] + dp[n][0][2] + dp[n][1][0] + dp[n][1][1] + dp[n][2][0]  + dp[n][2][2]) % MOD;
        cout << ans << endl;
    }
    
}

---
## Problem #1147 Syntax Checker
### 解題思路

- 字串從後往前遍歷，每一步更新目前的**句子數**

- 分情形討論：
- 遇到小寫：**句子數** + 1
- 遇到 $A$：
- 若當前的**句子數** $<1$，表示無法組成一個句子，直接跳出迴圈輸出 "NO"
- 否則，**句子數**不變
- 遇到 $B$：
- 若當前的**句子數** $<2$，表示無法組成一個句子，直接跳出迴圈輸出 "NO"
- 否則，**句子數** -1
- 遇到 $C$：
- 若當前的**句子數** $<3$，表示無法組成一個句子，直接跳出迴圈輸出 "NO"
- 否則，**句子數** -2

- 若迴圈有成功跑完，我們還需要判斷最終的**句子數**是否為 1
- 若是，輸出 "YES".
- 若否，輸出 "NO".

---
### 完整程式碼

#include<iostream>
#include<string>
using namespace std;

int main()
{
    int t = 0;
    cin >> t;
        for(int i = 0; i < t; i++)
        {
            string s;
            cin >> s;
            int len = s.length();
            int st = 0;
            bool res = true;
            if(!(s[0]  <= 'z' && s[0] >= 'a' && len > 1))
            {

                for(int j = len - 1; j >= 0; j--)
                {
                    if(s[j] <= 'z' && s[j] >= 'a')
                        st++;

                    if(s[j] == 'A' && st < 1)
                    {
                        res = false;
                        break;
                    }
                       

                    if(s[j] == 'B')
                    {
                        if(st >= 2) 
                            st--;
                        else
                        {
                            res = false;
                            break;
                        }
                    }
                    if(s[j] == 'C')
                    {
                        if(st >= 3) 
                            st -= 2;
                        else
                        {
                            res = false;
                            break;
                        }
                            
                    }
                }
            }
            if(st == 1 && res)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }


}