# Dynamic Programming

###### tags: `LeetCode筆記`

**在學習Dynamic Programming前必須要先了解Recursion和Greedy algorithm和Hash Table以及一些時間複雜度**

## :memo: 特性
* 動態規劃可以系統且有效率的探索一個問題的所有可能答案
* 要解的問題有兩種特性:
* 可以被拆分成重複的子問題(原問題的小版本)
* 最佳解可以由重複子問題的最佳解組成

## :memo: 費式數列 Fibonacci
要去解F(N)可以看成F(N的前第一項)+F(N的前第二項)的smaller subproblems，而這兩項有overlapping的項目像是F(N的前第三項)會在計算這兩項時使用到。
The brute force solution for calculating the Fibonacci sequence has **exponential** time complexity.
The dynamic programming solution will have **linear** time complexity.
Because it **reuses the results of subproblems** rather than recalculating the results for previously seen subproblems.

## :memo: 演算法比較
https://www.geeksforgeeks.org/comparison-among-greedy-divide-and-conquer-and-dynamic-programming-algorithm/
### Greedy
have optimal substructure, but **not overlapping** subproblems

### Divide and Conquer
break a problem into subproblems but these subproblems are **not overlapping**

## :memo: Top-down and Bottom-up
### Bottom-up (Tabulation)

// Pseudocode example for bottom-up
F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
    F[i] = F[i - 1] + F[i - 2]

### Top-down (Memoization)


// Pseudocode example for top-down
memo = hashmap
Function F(integer i):
    if i is 0 or 1: 
        return i
    if i doesn't exist in memo:
        memo[i] = F(i - 1) + F(i - 2)
    return memo[i]

### Which is better?
* A **bottom-up** implementation's runtime is usually **faster**, as **iteration** does not have the overhead that recursion does.
* A **top-down** implementation is usually much **easier to write**. This is because with **recursion**, the ordering of subproblems does not matter, whereas with tabulation, we need to go through a logical ordering of solving subproblems.

## :memo: When to Use DP
**The first characteristic** that is common in DP problems is that the problem will ask for **the optimum value (maximum or minimum) of something**, or **the number of ways there are to do something.**

For example:

* What is the minimum cost of doing...
* What is the maximum profit from...
* How many ways are there to do...
* What is the longest possible...
* Is it possible to reach a certain point...

**Note:**
* **Not all** DP problems follow this format, and not all problems that follow these formats should be solved **using DP**. **Sometimes**, a problem in this format (asking for the max/min/longest etc.) is meant to be solved **with a greedy algorithm**.

**The second characteristic** that is common in DP problems is that **future "decisions" depend on earlier decisions**. Deciding to do something at one step may affect the ability to do something in a later step. This characteristic is what makes a greedy algorithm invalid for a DP problem - we need to factor in results from previous decisions. Admittedly, this characteristic is not as well defined as the first one, and the best way to identify it is to go through some examples.

**Note:**
When you're solving a problem on your own and trying to decide if the second characteristic is applicable, assume it isn't, then try to think of a counterexample that proves a greedy algorithm won't work. If you can think of an example where earlier decisions affect future decisions, then DP is applicable.

**To summarize:**
Although, in general, if the problem has constraints that cause decisions to affect other decisions, such as using one element prevents the usage of other elements, then we should consider using dynamic programming to solve the problem.

## :memo: 一、Framework for DP Problems
### state
In a DP problem, a **state** is a set of variables that can sufficiently describe a scenario. These variables are called **state variables**, and we only care about **relevant ones**.

Every unique value of i represents a unique state.

1. A function or data structure that will compute/contain the answer to the problem for every given state.
2. A recurrence relation to transition between states. (complicated)
3. Base cases, so that our recurrence relation doesn't go on infinitely. (easy)

* typically, finding the recurrence relation is the most difficult part of solving a DP problem.
* When coming up with the base case(s) ask yourself: What state(s) can I find the answer to without using dynamic programming?

## :memo: House Robber (Medium)
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night.**

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight **without alerting the police.**



### 作法 C
* i, the index of a house.
* dp(i) or dp[i] that returns the maximum amount of money you can rob up to and including house i
* dp(i) = max(dp(i - 1), dp(i - 2) + nums[i])
* dp(0) = nums[0], dp(1) = max(nums[0], nums[1])

int rob(int* nums, int numsSize) {
    int memo[100] = {0};
    
    if (numsSize == 1)
    {
        return nums[0];
    }
    
    memo[0] = nums[0];
    memo[1] = fmax(nums[0], nums[1]);
    
    for (int i = 2; i < numsSize; i++)
    {
        memo[i] = fmax(memo[i - 1], memo[i - 2] + nums[i]);
    }
    
    return memo[numsSize - 1];
}

### 作法 C++

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        
        if (nums.size() == 1) {
            return nums[0];
        }
        else if (nums.size() == 2) {
            return max(nums[0], nums[1]);
        }
        
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        
        return dp[nums.size() - 1];
    }
};

## :memo: Min Cost Climbing Stairs (Easy)

### 作法 C
從前面兩個的dp[i-1], dp[i-2]之中選擇最少花費再加上本次i的花費，計算結果為dp[i]

#define MIN(a, b) ((a < b) ? a : b)

int dp[costSize];
memset(dp, 0, sizeof(dp));

dp[0] = cost[0];
dp[1] = cost[1];

for (int i = 2; i < costSize; i++) 
{
    dp[i] = MIN(dp[i - 1], dp[i - 2]) + cost[i];
}

return MIN(dp[costSize - 1], dp[costSize - 2]);

### 作法 State Reduction
**不利用array去紀錄**，而是僅以3個變數就完成的方法

int one_back = 0;
int two_back = 0;
int takeStep = 0;

for (int i = 2; i < costSize + 1;i++)
{
    int temp = one_back;
    one_back = one_back + cost[i - 1];
    two_back = two_back + cost[i - 2];
    takeStep = fmin(one_back, two_back);
    two_back = temp;
    one_back = takeStep;
}

return takeStep;

### 作法 C++

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1, 0);

        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }

        return dp[cost.size()];
    }
};

## :memo: N-th Tribonacci Number (Easy)

### 作法 DP: Space Optimisation

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        
        int prev3 = 0, prev2 = 1, prev1 = 1;
        
        for (int i = 3; i <= n; i++) {
            int curi = prev1 + prev2 + prev3;
            prev3 = prev2;
            prev2 = prev1;
            prev1 = curi;
        }
        
        return prev1;
    }
};

### 作法 DP: Performance Optimisation

class Solution {
public:
    int tribonacci(int n) {
        vector<int> dp(38, 0);
        
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
        }
        
        return dp[n];
    }
};

## :memo: Delete and Earn (Medium)

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

* Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete **every** element equal to nums[i] - 1 and **every** element equal to nums[i] + 1.

Return the **maximum number of points** you can earn by applying the above operation some number of times.

### 作法 C
本題先計算每一種數字共可以得到多少分，也記錄最大的數字，之後去以前面第二個的dp[i-2]加上本次所得分數和前面第一次dp[i-1]兩者取較大當dp[i]

int deleteAndEarn(int* nums, int numsSize){    
    int max_number = 0;
    int array[10001] = {0};
    int memo[10001] = {0};

    for (int i = 0; i < numsSize; i++)
    {
        array[nums[i]] += nums[i];
        if (nums[i] > max_number)
        {
            max_number = nums[i];
        }
    }

    if (numsSize == 1)
    {
        return nums[0];
    } 

    memo[0] = 0;
    memo[1] = array[1];

    for (int i = 2; i < 10001; i++)
    {
        memo[i] = fmax(memo[i - 1], memo[i - 2] + array[i]);       
    }

    return memo[max_number];
}

### 作法 最快code C++

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = 10001;

        //take the total sum by each number
        vector<int> sum(n, 0);
        vector<int> dp(n, 0);

        for (auto num : nums) {
            sum[num] += num;
        }    
        
        // method 1
        /*
        dp[0] = 0; // nums is {0,0,0......} freq can be anything
        dp[1] = sum[1]; // even if 0 is present,n it's not gonna affect it
        //  now apply the house robbing concept
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 2] + sum[i], dp[i - 1]);
        }
        return dp[n - 1];
        */
        
        // method 2
        // You can also use 2 variables instead of dp array
        int prev = 0;
        int curr = sum[1];
        int ans = 0;

        for (int i = 2; i < n; i++) {
            ans = max(prev + sum[i], curr);
            prev = curr; curr = ans;
        }
        return ans;
    }
};

## :memo: 二、Top-down to Bottom-up
First, in an interview, if you solve a problem with top-down, you may be asked to rewrite your solution in an iterative manner (using bottom-up) instead.
Second, as we mentioned before, **bottom-up usually is more efficient than top-down in terms of runtime**.
**Top-down是function，Bottom-up是array**，而要找最大時將初始值設為負無窮大，找最小時將初始值設為正無窮大

## :memo: 執行乘法運算的最高分數 (Hard)
#### 題目: Maximum Score from Performing Multiplication Operations


### 作法
本體使用了從頭尾兩端去做選擇的方法: left, n-1-(i-left)，首先要多安排size給dp[multipliers+1][multipliers+1]，之後從dp[i][left]開始left從i遞減，i從multipliers-1開始去操作

dp[i]代表使用到第幾個multiplier，dp[i][left]代表到從左邊數來第幾個index的nums

dp[i][left]會等於第i個index的num選(mult * nums[left] + dp[i + 1][left + 1])或不選(mult * nums[right] + dp[i + 1][left])的最大值

最後回傳dp[0][0]

int maximumScore(int* nums, int numsSize, int* multipliers, int multipliersSize){    
    int dp[1001][1001] = {0};    
    
    for (int i = multipliersSize - 1; i >= 0; i--)
    {
        for (int left = i; left >= 0; left--)
        {
            int mult = multipliers[i];
            int right = numsSize - 1 - (i - left); 
            dp[i][left] = fmax(mult * nums[left] + dp[i + 1][left + 1], mult * nums[right] + dp[i + 1][left]);
        }
    }
    
    return dp[0][0];
}

## :memo: *Longest Common Subsequence (Medium)

### vector 二維宣告:

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1, 0));

第一個for是col，第二個for是row，都是由長度-1到0
if T1[row] == T2[col]
then dp[row][col] = dp[row][col] + 1
else
then dp[row][col] = max(d[row + 1][col], dp[row][col + 1])

return dp[0][0]

### 作法 C

本題是經典題目，LCS，要會trace

int longestCommonSubsequence(char * text1, char * text2){
    int dp[1001][1001] = {0};
    
    for (int col = strlen(text2) - 1; col >= 0; col--)
    {
        for (int row = strlen(text1) - 1; row >= 0; row--)
        {
            if (text1[row] == text2[col])
            {
                dp[row][col] = dp[row + 1][col + 1] + 1;
            }
            else
            {
                dp[row][col] = fmax(dp[row + 1][col], dp[row][col + 1]);
            }
        }
    }
    
    return dp[0][0];
}

### 作法 C++

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        
        int t[n + 1][m + 1];
        
        for (int i = 0; i < n + 1; i++)
        {
            t[i][0] = 0;
        }
        
        for (int i = 1; i < m + 1; i++)
        {
            t[0][i] = 0;
        }
        
        for (int i = 1; i < n + 1; i++)
        {
            for (int j = 1; j < m + 1; j++)
            {
                if (text1[i - 1] == text2[j - 1]) t[i][j] = 1 + t[i - 1][j-1];
                else t[i][j] = max(t[i - 1][j], t[i][j - 1]);
            }
        }
        
        return t[n][m];   
    }
};

## :memo: Maximal Square (Medium)
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.



### 作法 C
先判斷該格子的左上方格子是否為1，是才要進行動態規劃，而該dp[i][j](邊長)會=(左邊一格,上面一格,左上一格)之中最小再加上1，再利用一個變數去更新最大

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    int dp[301][301] = {0};
    int rows = matrixSize;
    int cols = rows > 0 ?  *matrixColSize : 0;
    int max = 0;
    
    for (int i = 1; i <= rows; i++) 
    {
        for (int j = 1; j <= cols; j++)
        {
            if (matrix[i - 1][j - 1] == '1')
            {
                dp[i][j] = fmin(fmin(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
            max = fmax(max, dp[i][j]);
            // printf("%d ",dp[i][j]);
        }
        // printf("\n");
    }
    
    return max * max;
}

### 作法 C++

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        vector<vector<int>> dp(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
        int max_edge = 0;        
        
        for (int i = 1; i <= matrix.size(); i++) {
            for (int j = 1; j <= matrix[0].size(); j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
                max_edge = max(max_edge, dp[i][j]);
            }
        }
        
        // for (int i = 0; i <= matrix.size(); i++) {
        //     for (int j = 0; j <= matrix[0].size(); j++) {
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        
        return max_edge * max_edge;
    }
};

## :memo: Minimum Difficulty of a Job Schedule (Hard)

https://leetcode.com/explore/learn/card/dynamic-programming/632/common-patterns-in-dp-problems/4109/
### 作法 DP O(n^2 * d)

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size();
        
        if (n < d) {
            return -1;
        }
        
        vector<vector<int>> dp(n, vector<int>(d + 1, INT_MAX));        
        
        dp[n - 1][d] = jobDifficulty[n - 1];
        
        // 第d天剩下工作中最難是多少
        for (int i = n - 2; i >= 0; i--) {
            dp[i][d] = max(dp[i + 1][d], jobDifficulty[i]);
        }
        
        // 第day天剩下工作中最難是多少
        for (int day = d - 1; day > 0; day--) {
            for (int i = day - 1; i < n - (d - day); i++) {
                int hardest = 0;
                // 從第j工作到最後一個工作哪個最難
                // -> greedy算hardest最大值(最難工作)
                // 加上明天工作最高難度dp[j+1][day+1]
                // 和上一個dp[i][day]比較
                // -> greedy算dp[i][day]最小值
                for (int j = i; j < n - (d - day); j++) {
                    hardest = max(hardest, jobDifficulty[j]);
                    dp[i][day] = min(dp[i][day], hardest + dp[j + 1][day + 1]);
                }
            }
        }
        
        return dp[0][1];
    }
};

### 作法 Monotonic Stack O(n * d)

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        const int num_tasks = jobDifficulty.size();
        
        if (num_tasks < d)
            return -1;
        
        std::vector<int> table(num_tasks);
        std::vector<int> stack;
        stack.reserve(num_tasks);
        
        std::inclusive_scan(jobDifficulty.cbegin(), jobDifficulty.cend(), table.begin(),
            [](auto a, auto b) { return std::max(a, b); },
            std::numeric_limits<int>::min());
        
        std::vector<int> temp(num_tasks);
        
        for (int current_day = 2; current_day <= d; ++current_day) {
            std::fill(temp.begin(), temp.end(), std::numeric_limits<int>::max());
            
            stack.clear();
            
            for (int i = current_day - 1; i < num_tasks; ++i) {
                int current_value = jobDifficulty[i];
                
                temp[i] = table[i - 1] + current_value;
                
                while (!stack.empty() && jobDifficulty[stack.back()] <= current_value) {
                    temp[i] = std::min(temp[i], temp[stack.back()] - jobDifficulty[stack.back()] + current_value);
                    stack.pop_back();
                }
                
                if (!stack.empty()) {
                    temp[i] = std::min(temp[i], temp[stack.back()]);
                }
                
                stack.push_back(i);
            }
            
            table = temp;
        }
        
        return table[num_tasks - 1];
    }
};

## :memo: *換錢題型
### Coin Change 1 (Medium)
最少coin數量換錢


### 作法

int coinChange(int* coins, int coinsSize, int amount){
    int max = amount + 1;
    int dp[10001];
    for (int i = 0; i < 10001; i++)
    {
        dp[i] = max;    
    }    
    
    dp[0] = 0;
    for (int i = 1; i <= amount; i++)
    {
        for (int j = 0; j < coinsSize; j++)
        {
            if (coins[j] <= i)
            {
                dp[i] = fmin(dp[i], dp[i - coins[j]] + 1);    
            }            
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

### Coin Change 2 (Medium)
換錢方法數


### 作法
累加dp[j-coins[i]]

int change(int amount, int* coins, int coinsSize){
    int dp[5001] = {0};
    dp[0] = 1;
    
    for (int i = 0; i < coinsSize; i++)
    {
        for (int j = coins[i]; j < amount + 1; j++)
        {
            dp[j] += dp[j - coins[i]];
        }
    }
    
    return dp[amount];
}

## :memo: Word Break (Medium)



### 作法

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.length(), false);
        
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < wordDict.size(); j++) {
                if (i >= wordDict[j].length() - 1 && (i == wordDict[j].length() - 1 || dp[i - wordDict[j].length()])) {
                    if (s.substr(i - wordDict[j].length() + 1, wordDict[j].length()) == wordDict[j]) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            // cout<<dp[i]<<endl;
        }
        
        return dp[s.length() - 1];
    }
};

## :memo: Longest Increasing Subsequence (Medium)

### 作法 C
第一層for是以i為最大，去看第二層的for迴圈j最多可以遞增幾個，然後紀錄dp[i]，最後去看哪一個dp[i]有最大的值

int lengthOfLIS(int* nums, int numsSize){
    int dp[2501];
    for (int i = 0; i < 2501; i++)
    {
        dp[i] = 1;
    }
    
    for (int i = 1; i < numsSize; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (nums[i] > nums[j])
            {
                dp[i] = fmax(dp[i], dp[j] + 1);
            }
        }
    }
    
    int longest = 0;
    for (int i = 0; i < numsSize; i++)
    {
        longest = fmax(longest, dp[i]);
    }
    
    return longest;
}

### 作法 C++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int ans = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }

        return ans;
    }
};

## :memo: *買賣股票最佳時機題型
## 1. Best Time to Buy and Sell Stock (Easy)
回傳最大的一次價差


### 作法 C
記錄當前=fmin(current,prices[i])，最佳收益會是best與當時股票減當前取最小

int maxProfit(int* prices, int pricesSize){
    int best = INT_MIN;
    int current = INT_MAX;
    
    for (int i = 0; i < pricesSize; i++)
    {
        current = fmin(current, prices[i]);
        best = fmax(prices[i] - current, best);
    }
    
    return best;
}

### 作法 C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int lowest_price = INT_MAX;
        int highest_price = INT_MIN;
        int profit = INT_MIN;
        
        if (prices.size() == 1) {
            return 0;
        }
        
        for (int i = 0; i < prices.size(); i++) {
            highest_price = max(highest_price, prices[i]);
            profit = max(highest_price - lowest_price, profit);
            // cout<<highest_price<<" "<<lowest_price<<" "<<profit<<endl;
            lowest_price = min(lowest_price, prices[i]);
            if (lowest_price == prices[i]) {
                highest_price = prices[i];
            }
        }
        
        return profit;
    }
};

## 2. Best Time to Buy and Sell Stock II (Medium)
回傳一個時期買賣N次最大收益




### 作法 Peak Valley Approach

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;

        while (i < prices.size() - 1) {
            while (i < prices.size() - 1 and prices[i] >= prices[i + 1]) {
                i++;
            }
            valley = prices[i];
            while (i < prices.size() - 1 and prices[i] <= prices[i + 1]) {
                i++;
            }
            peak = prices[i];
            maxprofit += peak - valley;
        }

        return maxprofit;
    }
};

### 作法 Simple One Pass

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        
        for (int i = 0; i < prices.size() - 1; i++) {
            if (prices[i] < prices[i + 1]) {
                profit += prices[i + 1] - prices[i];
            }
        }
        
        return profit;
    }
};

## 3. Best Time to Buy and Sell Stock III (Hard)
回傳一個時期最多買賣2次最大收益




### 作法 Bidirectional Dynamic Programming

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) {
            return 0;
        }

        int leftMin = prices[0];
        int rightMax = prices[n - 1];

        vector<int> leftProfits(n, 0);
        vector<int> rightProfits(n + 1, 0);

        for (int l = 1; l < n; l++) {
            leftProfits[l] = max(leftProfits[l - 1], prices[l] - leftMin);
            leftMin = min(leftMin, prices[l]);

            int r = n - 1 - l;
            rightProfits[r] = max(rightProfits[r + 1], rightMax - prices[r]);
            rightMax = max(rightMax, prices[r]);
        }

        int maxProfit = 0;
        for (int i = 0; i < n; i++) {
            maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i + 1]);
        }

        return maxProfit;
    }
};

### 作法 One-pass Simulation

class Solution {
  public:
    int maxProfit(vector<int>& prices) {
        int t1Cost = INT_MAX, 
            t2Cost = INT_MAX;
        int t1Profit = 0,
            t2Profit = 0;
            
        /*  變數擺放位置
            A = ,price)
            B = ,price-掉A)
            C = ,price-掉B)
            D = ,price-掉C)
        */
        
        for (int price : prices) {
            // the maximum profit if only one transaction is allowed
            t1Cost = min(t1Cost, price);
            t1Profit = max(t1Profit, price - t1Cost);
            // re-invest the gained profit in the second transaction
            t2Cost = min(t2Cost, price - t1Profit);
            t2Profit = max(t2Profit, price - t2Cost);
        }

        return t2Profit;
    }
};

## 4. Best Time to Buy and Sell Stock IV (Hard)
最大允許k次交易，回傳數次交易後最大收益


### 作法

int maxProfit(int k, int* prices, int pricesSize){
    int dp[1001][101][2] = {0};
    
    for (int i = pricesSize - 1; i >= 0; i--)
    {
        for (int transactionsRemaining = 1; transactionsRemaining <= k; transactionsRemaining++)
        {
            for (int holding = 0; holding < 2; holding++)
            {
                int doNothing = dp[i + 1][transactionsRemaining][holding];
                int doSomething;
                if (holding == 1)
                {
                    // Sell stock
                    doSomething = prices[i] + dp[i + 1][transactionsRemaining - 1][0];
                }
                else
                {
                    // Buy stock
                    doSomething = (-1) * prices[i] + dp[i + 1][transactionsRemaining][1];
                }
                // Recurrence relation
                dp[i][transactionsRemaining][holding] = fmax(doNothing, doSomething);
            }
        }
    }
    
    return dp[0][k][0];
}

### 迷之最快code

#include <immintrin.h>
class Solution {
public:

    int __attribute__((target("avx512f"))) maxProfit(int K, vector<int>& prices) {
        vector<int> q0(K+1), q1(K+1);
        vector<int> qn0(K+1), qn1(K+1);
        for(int i = prices.size()-1; i>=0; i--) {
            int k = 1;
            __m512i pri = _mm512_set1_epi32(prices[i]);
            for(; k + 16 <= K; k+=16) {
                __m512i q0km1 = _mm512_loadu_si512((__m512i*)&q0[k-1]);
                __m512i q1k = _mm512_loadu_si512((__m512i*)&q1[k]);
                __m512i q0k = _mm512_loadu_si512((__m512i*)&q0[k]);
                __m512i do_sell = _mm512_add_epi32(pri, q0km1);
                __m512i dont_sell = q1k;
                __m512i do_buy = _mm512_sub_epi32(q1k, pri);
                __m512i dont_buy = q0k;
                _mm512_storeu_si512((__m512i*)&qn1[k], _mm512_max_epi32(do_sell, dont_sell));
                _mm512_storeu_si512((__m512i*)&qn0[k], _mm512_max_epi32(do_buy, dont_buy));
            }
            for(; k <= K; k++) {
                int do_sell = prices[i] + q0[k-1];
                int dont_sell = q1[k];
                qn1[k] = max(do_sell, dont_sell);
                int do_buy = -prices[i] + q1[k];
                int dont_buy = q0[k];
                qn0[k] = max(do_buy, dont_buy);
            }
            swap(q0, qn0);
            swap(q1, qn1);
        }
        return q0[K];
    }
};

## 5. Best Time to Buy and Sell Stock with Cooldown (Medium)
在賣股票後需冷靜一天的買法(不限買賣的次數)


### 作法


int maxProfit(int* prices, int pricesSize){
    int sold = INT_MIN;
    int held = INT_MIN;
    int reset = 0;
    
    for (int i = 0; i < pricesSize; i++)
    {
        int preSold = sold;
        sold = held + prices[i];
        held = fmax(held, reset - prices[i]);
        reset = fmax(reset, preSold);
    }
    
    return fmax(sold, reset);
}

### 作法 最快code

class Solution {
public:
    int f( vector<int>&p,int i,int buy, vector<vector<int>>&dp ){
        if (i >= p.size()) return 0;
        if (dp[i][buy] != -1) return dp[i][buy];
        if (buy == 0){
            return dp[i][buy] = max(f(p, i + 1, buy, dp), -p[i] + f(p, i + 1, 1, dp));
        }
        if (buy == 1){
            return dp[i][buy] = max(f(p, i + 1, buy, dp), p[i] + f(p, i + 2, 0, dp));
        }
        return 0;
    }
    int maxProfit(vector<int>& prices) {
        vector<vector<int>>dp(prices.size(), vector<int>(2, -1));
        return f(prices, 0, 0, dp);
    }
};

## 6. Best Time to Buy and Sell Stock with Transaction Fee (Medium)
賣股票需付手續費(不限買賣的次數)


### 作法
cash為不賣或賣的現金取大，hold為不買或買的持有取大

int maxProfit(int* prices, int pricesSize, int fee){   
    int cash = 0;
    int hold = (-1) * prices[0];
    
    for (int i = 1; i < pricesSize; i++)
    {
        cash = fmax(cash, hold + prices[i] - fee);
        hold = fmax(hold, cash - prices[i]);
    }
    
    return cash;
}

## :memo: 三、State Reduction
優化空間複雜度
Using only two variables instead, we can improve space complexity to O(1) from O(n) using an array.
### 費氏數列

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1: return n
        one_back = 1
        two_back = 0
        for i in range(2, n + 1):
            temp = one_back
            one_back += two_back
            two_back = temp

        return one_back

## :memo: Paint Fence (Medium)


### 作法

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 1) {
            return k;
        }
        if (n == 2) {
            return k * k;
        }
        
        int totalWays[51];
        totalWays[1] = k;
        totalWays[2] = k * k;
        
        for (int i = 3; i <= n; i++) {
            //第一項是最後一個fence和前一個fence顏色不同,
            //第二項是最後一個fence和前一個fence顏色相同，
            //所以第一項是i-1,第二項是i-2
            totalWays[i] = (k - 1) * totalWays[i - 1] + (k - 1) * totalWays[i - 2];    
        }
        
        return totalWays[n];
    }
};

## :memo: Decode Ways (Medium)



stoi(string str)
將str轉乘int

### 作法

class Solution {
public:
    int numDecodings(string s) {
        vector<int> dp(s.length() + 1, 0);
        dp[0] = 1;        
        dp[1] = s[0] == '0' ? 0 : 1;
        
        for (int i = 2; i < dp.size(); i++) {
            if (s[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }            
            int two_digit = stoi(s.substr(i - 2, 2));
            if (two_digit >= 10 && two_digit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[s.length()];
    }
};

## :memo: 四、Kadane's Algorithm

// Given an input array of numbers "nums",
1. best = negative infinity
2. current = 0
3. for num in nums:
    3.1. current = Max(current + num, num)
    3.2. best = Max(best, current)

4. return best

## :memo: Maximum Sum Circular Subarray (Medium)


### 作法 Calculate the "Minimum Subarray"

int maxSubarraySumCircular(int* nums, int numsSize) {
    int maxcurrent = nums[0];
    int maxsum = nums[0];
    int mincurrent = nums[0];
    int minsum = nums[0];
    int sum = nums[0];
    
    for (int i = 1; i < numsSize; i++)
    {
        sum += nums[i];
        maxcurrent = fmax(maxcurrent + nums[i], nums[i]);
        maxsum = fmax(maxsum, maxcurrent);
        mincurrent = fmin(mincurrent + nums[i], nums[i]);
        minsum = fmin(minsum, mincurrent);
    }
    
    if (sum == minsum)
    {
        return maxsum;
    }
    
    return fmax(sum - minsum, maxsum);
}

### 作法 Enumerate prefix and suffix sums

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        const int n = nums.size();
        
        vector<int> right_max(n);        
        right_max[n - 1] = nums[n - 1];        
        for (int suffix_sum = nums[n - 1], i = n - 2; i >= 0; --i) {
            suffix_sum += nums[i];
            right_max[i] = max(right_max[i + 1], suffix_sum);
        }
        
        int max_sum = nums[0];
        int special_sum = nums[0];        
        for (int i = 0, prefix_sum = 0, curMax = 0; i < n; ++i) {
            curMax = max(curMax, 0) + nums[i];
            max_sum = max(max_sum, curMax);
            prefix_sum += nums[i];
            if (i + 1 < n) {
                special_sum = max(special_sum, prefix_sum + right_max[i + 1]);
            }
        }
        
        return max(max_sum, special_sum);
    }
};

## :memo: 五、Pathing Problems

If we are allowed to move in all 4 directions, then it might be a graph/BFS problem instead.
This pattern is sometimes combined with other patterns we have looked at, such as **counting DP(計算次數)**.

## :memo: Unique Paths (Medium)


### 作法 C
dp[i][j] = dp左邊一格 + dp上面一格

int uniquePaths(int m, int n) {
    int dp[100][100];
    
    for (int i = 0; i < m; i++)
    {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++)
    {
        dp[0][j] = 1;
    }
    
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            // printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);
        }
    }
    
    return dp[m - 1][n - 1];
}

### 作法 C++

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        dp[0][0] = 1;
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (row > 0) {
                    dp[row][col] = dp[row - 1][col];
                }
                if (col > 0) {
                    dp[row][col] += dp[row][col - 1];
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
};

## :memo: Unique Paths II obstacle (Medium)


### 作法
先將第一行第一列的方法數確定完畢
最後多一個判斷式檢查是否有障礙物

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int dp[100][100];
    
    if (obstacleGrid[0][0] == 1)
    {
        return 0;
    }
    
    dp[0][0] = 1;
    
    for (int i = 1; i < obstacleGridSize; i++)
    {
        if (obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1)
        {
            dp[i][0] = 1;    
        }
        else
        {
            dp[i][0] = 0;
        }
    }
    for (int j = 1; j < *obstacleGridColSize; j++)
    {
        if (obstacleGrid[0][j] == 0 && dp[0][j - 1] == 1)
        {
            dp[0][j] = 1;    
        }        
        else
        {
            dp[0][j] = 0; 
        }
    }
    
    for (int i = 1; i < obstacleGridSize; i++)
    {
        for (int j = 1; j < *obstacleGridColSize; j++)
        {
            if (obstacleGrid[i][j] == 0)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];    
            }
            else
            {
                dp[i][j] = 0;
            }
            // printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);
        }
    }
    
    return dp[obstacleGridSize - 1][(*obstacleGridColSize) - 1];
}

### 作法 C++ 0ms

class Solution {
 public:
  int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    const int m = obstacleGrid.size();
    const int n = obstacleGrid[0].size();
    // dp[i][j] := unique paths from (0, 0) to (i - 1, j - 1)
    vector<vector<long>> dp(m + 1, vector<long>(n + 1, 0));
    dp[0][1] = 1;  // Can also set dp[1][0] = 1

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (!obstacleGrid[i - 1][j - 1])
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

    return dp[m][n];
  }
};

## :memo: Minimum Path Sum (Medium)


### 作法 C
在計算dp時加的是該格子的數值

int minPathSum(int** grid, int gridSize, int* gridColSize){
    int dp[200][200];
    int i = 0;
    int j = 0;
    
    dp[0][0] = grid[0][0];
    
    for (int i = 1; i < gridSize; i++)
    {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    
    for (int j = 1; j < *gridColSize; j++)
    {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    
    for (int i = 1; i < gridSize; i++)
    {
        for (int j = 1; j < *gridColSize; j++)
        {
            dp[i][j] = fmin(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
        // printf("%d\n",dp[i][j]);
    }
    
    return dp[gridSize - 1][*gridColSize - 1];
}

### 作法 C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (row - 1 >= 0 and col - 1 >= 0) {
                    dp[row][col] = min(dp[row - 1][col] + grid[row][col], dp[row][col - 1] + grid[row][col]);    
                }
                else if (row - 1 >= 0 and col - 1 < 0) {
                    dp[row][col] = dp[row - 1][col] + grid[row][col];
                }
                else if (col - 1 >= 0 and row - 1 < 0) {
                    dp[row][col] = dp[row][col - 1] + grid[row][col];
                }
                else {
                    dp[row][col] = grid[row][col];
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
};

## :memo: Minimum Falling Path Sum (Medium)


### 作法 C
要先判斷是否為邊邊(0,n-1)，三種case由上往下只能留左下或右下一格，最後挑出最下面一列之中sum最小的dp[i][j]

int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize){
    int dp[100][100];
    int row = 0;
    int col = 0;
    int min = INT_MAX;
    
    for (int col = 0; col< *matrixColSize; col++)
    {
        dp[0][col] = matrix[0][col];
    }
    
    for (int row = 1; row < matrixSize; row++)
    {
        for (int col = 0; col < *matrixColSize; col++)
        {
            if (col == 0)
            {
                dp[row][col] = fmin(dp[row - 1][col],dp[row - 1][col + 1]) + matrix[row][col];
            }
            else if (col == *matrixColSize - 1)
            {
                dp[row][col] = fmin(dp[row - 1][col - 1],dp[row - 1][col]) + matrix[row][col];
            }
            else
            {
                dp[row][col] = fmin(fmin(dp[row - 1][col - 1], dp[row - 1][col]), dp[row - 1][col + 1]) + matrix[row][col];
            }
            // printf("%d\n",dp[row][col]);
        }
    }
    // printf("=========\n");
    for (int col = 0; col < *matrixColSize; col++)
    {
        // printf("%d\n",dp[matrixSize-1][col]);
        min = fmin(dp[matrixSize - 1][col], min);
    }
    
    return min;
}

### 作法 C++

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int ans = INT_MAX;
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (row == 0) {
                    dp[row][col] = matrix[row][col];
                }
                else if (col == 0) {
                    dp[row][col] = min(dp[row - 1][col] + matrix[row][col], dp[row - 1][col + 1] + matrix[row][col]);
                }
                else if (col == n - 1) {
                    dp[row][col] = min(dp[row - 1][col] + matrix[row][col], dp[row - 1][col - 1] + matrix[row][col]);
                }
                else {
                    dp[row][col] = min(min(dp[row - 1][col] + matrix[row][col], dp[row - 1][col - 1] + matrix[row][col]), dp[row - 1][col + 1] + matrix[row][col]);
                }
            }            
        }
        for (int col = 0; col < n; col++) {
            ans = min(ans, dp[m - 1][col]);
        }
        
        return ans;
    }
};

## :memo: 六、More Practice Problems
**Practice makes perfect!**

https://leetcode.com/explore/learn/card/dynamic-programming/647/more-practice-problems/

## :memo: Paint House (Medium) 3 colors
There is a row of **n** houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an **n x 3** cost matrix **costs**.

* For example, **costs[0][0]** is the cost of painting house **0** with the color red; **costs[1][2]** is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.


### 作法

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        vector<vector<int>> dp(costs.size(), vector<int>(costs[0].size(), 0));
        
        for (int col = 0; col < costs[0].size(); col++) {
            dp[0][col] = costs[0][col];
        }
        
        for (int row = 1; row < costs.size(); row++) {
            for (int col = 0; col <costs[0].size(); col++) {
                if (col == 0) {
                    dp[row][col] = min(dp[row - 1][col + 1] + costs[row][col], dp[row - 1][col + 2] + costs[row][col]);
                }
                else if (col == 1) {
                    dp[row][col] = min(dp[row - 1][col + 1] + costs[row][col], dp[row - 1][col - 1] + costs[row][col]);
                }
                else {
                    dp[row][col] = min(dp[row - 1][col - 1] + costs[row][col], dp[row - 1][col - 2] + costs[row][col]);
                }
            }
        }
        
        int ans = INT_MAX;
        for (int col = 0; col < costs[0].size(); col++) {
            ans = min(ans, dp[costs.size() - 1][col]);    
        }
        
        return ans;
    }
};

## :memo: Paint House II (Hard) k colors
變成 k 種顏色

### 作法 DP with Optimized Time
**時間: O(n * k)**

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        if (costs.size() == 0) {
            return 0;
        }
        int n = costs.size();
        int k = costs[0].size();
        int MinColor = 0;
        int secondMinColor = 0;
        
        for (int house = 1; house < n; house++) {
             // Find the minimum and second minimum color in the PREVIOUS row.
            MinColor = -1;
            secondMinColor = -1;
            for (int color = 0; color < k; color++) {
                int cost = costs[house - 1][color];
                if (MinColor == -1 || cost < costs[house - 1][MinColor]) {
                    secondMinColor = MinColor;
                    MinColor = color;
                }
                else if (secondMinColor == -1 || cost < costs[house - 1][secondMinColor]) {
                    secondMinColor = color;
                }
            }
            
            // And now calculate the new costs for the current row.
            for (int color = 0; color < k; color++) {
                if (color == MinColor) {
                    costs[house][color] += costs[house - 1][secondMinColor]; 
                }
                else {
                    costs[house][color] += costs[house - 1][MinColor];
                }
            }
        }
        
        
        // Find the minimum in the last row
        int ans = INT_MAX;
        for (int c : costs[n - 1]) {
            ans = min(ans, c);
        }
        
        return ans;
    }
};

## :memo: Paint House III (Hard)
There are a row of **n** houses, each house can be painted with one of the **k** colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an **n x k** cost matrix costs.

* For example, **costs[0][0]** is the cost of painting house **0** with color **0**; **costs[1][2]** is the cost of painting house 1 with color 2, and so on...

Return the minimum cost to paint all houses.


### 作法
三維陣列[房子][鄰居群][顏色]
要判斷前1棟顏色算成本

class Solution {
public:
    // Maximum cost possible plus 1
    const int MAX_COST = 1000001;
    
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        // Initialize memo array
        vector<vector<vector<int>>> memo(m, vector<vector<int>>(target + 1, vector<int>(n, MAX_COST)));
        
        // Initialize for house 0, neighborhoods will be 1
        for (int color = 1; color <= n; color++) {
            if (houses[0] == color) {
                // If the house has same color, no cost
                memo[0][1][color - 1] = 0;
            }
            else if (!houses[0]) {
                // If the house is not painted, assign the corresponding cost
                memo[0][1][color - 1] = cost[0][color - 1];
            }
        }
        
        for (int house = 1; house < m; house++) {
            for (int neighborhoods = 1; neighborhoods <= min(target, house + 1); neighborhoods++) {
                for (int color = 1; color <= n; color++) {
                    // If the house is already painted, and color is different
                    if (houses[house] && color != houses[house]) {
                        // Cannot be painted with different color
                        continue;
                    }
                    
                    int currCost = MAX_COST;
                    
                    // Iterate over all the possible color for previous house
                    for (int prevColor = 1; prevColor <= n; prevColor++) {
                        if (prevColor != color) {
                            // Decrement the neighborhood as adjacent houses has different color
                            currCost = min(currCost, memo[house - 1][neighborhoods - 1][prevColor - 1]);
                        }
                        else {
                            // Previous house has the same color, no change in neighborhood count
                            currCost = min(currCost, memo[house - 1][neighborhoods][color - 1]);
                        }
                    }
                    
                    // If the house is already painted cost to paint is 0
                    int costToPaint = houses[house] ? 0 : cost[house][color - 1];
                    memo[house][neighborhoods][color - 1] = currCost + costToPaint;
                }
            }
        }
        
        int minCost = MAX_COST;
        
        // Find the minimum cost with m houses and target neighborhoods
        // By comparing cost for different color for the last house
        for (int color = 1; color <= n; color++) {
            minCost = min(minCost, memo[m - 1][target][color - 1]);
        }
        
        // Return -1 if the answer is MAX_COST as it implies no answer possible
        return minCost == MAX_COST ? -1 : minCost;
    }
};

### 作法 最快code

class Solution {
    inline static const int MAX_COST = 20'000'00; 

    int target;
    int m;
    int n;
    vector<int> houses;
    vector<vector<int>> cost;
    vector<int> memo;

    int dp(int idx, int left_ncount, int prev_color) {
        if (m - idx < left_ncount) return MAX_COST;
        if (left_ncount < 0) return MAX_COST;
        if (idx >= m) return 0;

        int key = idx + m * (left_ncount + m * prev_color);
        if (memo[key] != -1) return memo[key];

        memo[key] = MAX_COST;
        if (houses[idx] != 0) 
          memo[key] = min(memo[key], dp(idx + 1, 
                  left_ncount - (prev_color != houses[idx]), houses[idx]));
        else {
            for (int i = 1; i <= n; ++i) {
                memo[key] = min(memo[key], cost[idx][i - 1] + dp(idx + 1, left_ncount - (prev_color != i), i));
            }
        }
        return memo[key];
    }

    public:
        int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
            this->memo.assign((m + 1) * (m + 1) * (n + 1), -1);
            this->target = target;
            this->houses = move(houses);
            this->cost = move(cost);  
            this->n = n;
            this->m = m;

            int ans = dp(0, target, 0);
            return ans == MAX_COST ? -1 : ans;
    }
};

## :memo: Count Vowels Permutation (Hard)


### 作法 DP array

class Solution {
public:
    int countVowelPermutation(int n) {
        vector<vector<long long>> dp(n, vector<long long>(5, 0));
        
        for (int i = 0; i < 5; i++) {
            dp[0][i] = 1;
        }
        
        for (int i = 1; i < n; i ++) {
            for (int j = 0; j < 5; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4];
                }
                else if (j == 1) {
                    dp[i][j] = dp[i - 1][0] + dp[i - 1][2];
                }
                else if (j == 2) {
                    dp[i][j] = dp[i - 1][1] + dp[i - 1][3];
                }
                else if (j == 3) {
                    dp[i][j] = dp[i - 1][2];
                }
                else {
                    dp[i][j] = dp[i - 1][2] + dp[i - 1][3];
                }
                dp[i][j] = dp[i][j] % 1000000007;
            }
        }
        
        long long ans = 0;
        
        for (int i = 0; i < 5; i++) {
            ans += dp[n - 1][i];
        }
        
        return ans % 1000000007;
    }
};

### 作法 完全沒有if
很快但是不能記錄中間的n有幾種

class Solution {
public:
    int countVowelPermutation(int n) {
      long a = 1, e = 1, i = 1, o = 1, u = 1, mod = pow(10, 9)+7;

        long a2, e2, i2, o2, u2; 

        

        for (int j = 2; j <= n; j++) {

            a2 = (e + i + u) % mod;

            e2 = (a + i) % mod;

            i2 = (e + o) % mod;

            o2 = i;

            u2 = (o + i) % mod;

            

            a = a2, e = e2, i = i2, o = o2, u = u2;

        }

        return (a + e + i + o + u) % mod;
    
      
       
    }
};

## :memo: 重複子數組的最大長度 (Medium)
#### 題目:Maximum Length of Repeated Subarray


### 作法
dp記錄相同prefix長度，之後要從n-1,m-1陣列尾巴去往回算
if nums1[i] == nums2[j], dp[i][j] = dp[i+1][j+1] + 1

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int ans = INT_MIN;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                }
                ans = max(ans, dp[i][j]);
            }
        }
        
        return ans;
    }
};

## :memo: *具有目標總和的骰子擲數 (Medium)
#### 題目: Number of Dice Rolls With Target Sum
You have **n** dice, and each die has **k** faces numbered from **1** to **k**.

Given three integers **n**, **k**, and **target**, return the number of possible ways (out of the **k^n** total ways) to roll the dice, so the sum of the face-up numbers equals **target**. Since the answer may be too large, return it modulo **10^9 + 7**.


### 作法
要從n - 1開始
column size = target大小
dp[n][target] = 1

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
        int mod = pow(10, 9) + 7;        

        dp[n][target] = 1;        
        
        for (int diceIndex = n - 1; diceIndex >= 0; diceIndex--) {
            for (int currSum = 0; currSum < target; currSum++) {
                int ways = 0;
                
                for (int i = 1; i <= min(k, target - currSum); i++) {
                    ways = (ways + dp[diceIndex + 1][currSum + i]) % mod;
                }
                
                dp[diceIndex][currSum] = ways;
            }
        }
        
        return dp[0][0];
    }
};

## :memo: Domino and Tromino Tiling (Medium)


### 作法
這題要把缺一角記做p[k]
f[k]記做完整
所以f[k] = f[f-1] + f[k-2] + 2 * p[k-1]
而p[k] = p[k-1] + f[k-2]

class Solution {
public:
    int numTilings(int n) {
        int mod = 1000000007;
        
        if (n <= 2) {
            return n;
        }
        
        long f[n + 1];
        
        long p[n + 1];
        
        f[1] = 1L;
        f[2] = 2L;
        p[2] = 1L;
        
        for (int k = 3; k < n + 1; k++) {
            f[k] = (f[k - 1] + f[k - 2] + 2 * p[k - 1]) % mod;
            p[k] = (p[k - 1] + f[k - 2]) % mod;
        }
        
        return f[n];
    }
};

### 作法 數學

class Solution {
public:
    int numTilings(int n) {
        if (n <= 2) {
            return n;
        }
            
        if (n == 3) {
            return 5;
        }
            
        //a = n(1), b = n(2), c = n(3)
        long res, a = 1, b = 2, c = 5;
        while (n-- > 3) {
            res = (2*c + a) % int (1e9 + 7);
            //shift a,b,c to the right
            a = b;
            b = c;
            c = res;
        }
        
        return res;
    }
};

## :memo: Minimum Cost For Tickets (Medium)


### 作法
準備一年的array，然後標記要看的天數，for迴圈跑到該天數dp紀錄日票還是周票還是月票
int x = max(i - 1, 0);
int y = max(i - 7, 0);
int z = max(i - 30, 0);
dp[i] = min(min(dp[x] + costs[0], dp[y] + costs[1]), dp[z] + costs[2]);
如果不是標記日:
else {
dp[i] = dp[i-1];
}

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int dp[366] = {0};
        int marked[366] = {0};

        for (int i = 0; i < days.size(); i++) {
            marked[days[i]] = 1;
        }

        for (int i = 1; i < 366; i++) {
            if (marked[i] == 1) {
                int x = max(i - 1, 0);
                int y = max(i - 7, 0);
                int z = max(i - 30, 0);
                dp[i] = min(min(dp[x] + costs[0], dp[y] + costs[1]), dp[z] + costs[2]);    
            }
            else {
                dp[i] = dp[i-1];
            }           
        }

        return dp[365];
    }
};

## :memo: Interleaving String (Medium)


### 作法
用2維DP陣列紀錄

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }       
    
        bool dp[s1.length() + 1][s2.length() + 1];

        for (int i = 0; i < s1.length() + 1; i++) {
            for (int j = 0; j < s2.length() + 1; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                }                    
                else if (i == 0) {
                    dp[i][j] = (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
                }                    
                else if (j == 0) {
                    dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]);
                }                    
                else {
                    dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
                }
                    
            }
        }            

        return dp[s1.length()][s2.length()];
    }
};

## :memo: Longest Valid Parentheses (Hard)
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.


### 作法 Brute Force
**時間: O(N^3)**
**空間: O(N)**
費時: **Time Limit Exceeded** ms

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                st.push('(');
            } else if (!st.empty() and st.top() == '(') {
                st.pop();
            } else {
                return false;
            }
        }
        return st.empty();
    }

    int longestValidParentheses(string s) {
        int maxlen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 2; j <= s.length(); j += 2) {
                if (isValid(s.substr(i, j - i))) {
                    maxlen = max(maxlen, j - i);
                }
            }
        }

        return maxlen;
    }
};

### 作法 Dynamic Programming
**時間: O(N)** Time: 6 ms
**空間: O(N)** Memory: 7.64 MB


**第2點想不到!!!**

public:
    int longestValidParentheses(string s) {
        int maxans = 0;
        vector<int> dp(s.length(), 0);

        for (int i = 1; i < s.length(); i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = max(maxans, dp[i]);
            }
        }

        return maxans;
    }
};

### 作法 Stack
**時間: O(N)** Time: 6 ms
**空間: O(N)** Memory: 7.56 MB
如果空就放括號，空的時候放的是右括號代表長度從這index以前不要算，持續更新新的右括號的index取代舊的右括號的index

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0;
        stack<int> st;

        st.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                } else {
                    maxans = max(maxans, i - st.top());
                }
            }
        }

        return maxans;
    }
};

### 作法 Without extra space
**時間: O(N)** Time: 6 ms
**空間: O(N)** Memory: 7.22 MB
從左掃到右可以想到，**但是從右再掃到左想不到。**

class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, maxlength = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }

        left = 0, right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }

        return maxlength;
    }
};

## :memo: Range Sum Query 2D - Immutable (Medium)


### 作法 Caching Smarter

class NumMatrix {
public:
    int dp[201][201] = {0};
    
    NumMatrix(vector<vector<int>>& matrix) {     
        for (int r = 0; r < matrix.size(); r++) {
            for (int c = 0; c < matrix[0].size(); c++) {
                dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
            }
        }        
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];

    }
};

## :memo: Knight Dialer (Medium)

標準的二維DP，row記錄現在是第幾個digit，col紀錄是哪一個號碼，第i個digit有j個號碼，再由k代表由j的下一個可到達號碼，三層FOR迴圈
最後把所有dp[9][j]加起來，數量龐大要MOD
### 作法

class Solution {
public:
    int knightDialer(int n) {
        vector<vector<int>> move = { {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};
        int MOD = 1e9 + 7;
        vector<vector<int>> dp(n, vector(10, 0));
        
        for (int square = 0; square < 10; square++) {
            dp[0][square] = 1;
        }

        for (int remain = 1; remain < n; remain++) {
            for (int square = 0; square < 10; square++) {
                int ans = 0;
                for (int nextSquare : move[square]) {
                    ans = (ans + dp[remain - 1][nextSquare]) % MOD;
                }
                dp[remain][square] = ans;
            }
        }

        int ans = 0;
        for (int square = 0; square < 10; square++) {
            ans = (ans + dp[n - 1][square]) % MOD;
        }

        return ans;
    }
};

## :memo: 刷題檢討
在思考如何寫recurrence relation時，要去想這一步是否要去執行(取或不取)，由state去思考演算法，思考哪個東西加1後會影響到題目給的單位，dp array是由左到右，由上到下，隨著for迴圈的層數增加，要思考的state就越多，用紙和筆寫下作法，有時i從n-1開始有時i從0開始，動態規劃有兩種:1.計算總共方法數2.找出最大最小值，兩者都會受前一項影響