# Dynamic Programing

# 198. House Robber
## Question (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.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
## Solution (C++)

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

## Notes:
* 1-d的dp問題，**通常**都從index=2開始解
* 這題的核心概念就是line 11
* 判斷是否要rob index i，計算max(nums[i]+nums[i-2], nums[i-1], nums[i]+nums[i-3])

---

# 322. Coin Change
## Question
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1
Example 3:

Input: coins = [1], amount = 0
Output: 0
## Solution (C++)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int* dp = new int[amount+2]{};
        for(int i=0; i<=amount; i++)
            dp[i] = INT_MAX;
        dp[0] = 0;
        for(int i=0; i<coins.size(); i++){
            for(int j=coins[i]; j<=amount; j++){
                if(dp[j-coins[i]]==INT_MAX)
                    continue;
                dp[j] = min(dp[j], 1 + dp[j-coins[i]]);
            }
        }
        return (dp[amount]==INT_MAX)?-1:dp[amount];
    }
};

## Notes:
* 假設COINS = [2,3], AMOUNT=7
* 我們可以得到dp[2] = min(dp[2],1+dp[2-2]) = 1
* 當j=3的時候，因為幣值只有2，所以3是沒辦法找錢的，這個時候就需要第10行的判斷式。

---
# 300. Longest Increasing Subsequence
## Question (Medium)
Given an integer array nums, return the length of the longest strictly increasing
subsequence
.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1
## Solution (C++)

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

## Notes:
* 尚未實作O(NlogN)的解

---
# 5. Longest Palindromic Substring
## Question (Medium)
Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:

Input: s = "cbbd"
Output: "bb"
## Solution (C++)

class Solution {
public:
    string longestPalindrome(string s) {
        int** dp = new int*[s.length()]{};
        for(int i=0; i<s.length(); i++){
            dp[i] = new int[s.length()]{};
            dp[i][i] = 1;
        }
        int start = 0;
        int end = 0;
        int maxima = INT_MIN;
        for(int i=s.length()-1; i>=0; i--){
            for(int j=i+1; j<s.length(); j++){
                if(s[i]==s[j]){
                    if(j-i==1 || dp[i+1][j-1]==1){
                        dp[i][j] = 1;
                        if((j-i+1) > maxima){
                            maxima = (j-i+1);
                            start = i;
                            end = j;
                        }
                    }
                }
            }
        }
        string ans = "";
        for(int i=start; i<=end; i++)
            ans+=s[i];
        return ans;
    }
};

## Notes
* dp[i][j]表示s[i]~s[j]是否為Palindromic Substring，我覺得只要想出這個點，這題就很好解了。
* dp[i+1][j-1]這個用法也很讚，完全沒想到QQ

---

# 647. Palindromic Substrings
## Question (Medium)
Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa"
## Solution (C++)

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;
        int** dp = new int*[s.length()];
        for(int i=0; i<s.length(); i++){
            dp[i] = new int[s.length()]{};
            dp[i][i] = 1;
        } 
        for(int i=s.length()-1; i>=0; i--){
            for(int j=i+1; j<s.length(); j++){
                if(s[i] == s[j]&&(j-i==1||dp[i+1][j-1]==1)){
                    dp[i][j] = 1;
                    count++;
                }
            }
        }
        return count+s.length();
    }
};

## Notes
* 基本上跟**5. Longest Palindromic Substring**很像
* 計算整個dp 2-d array有幾個1即可

---

# 62. Unique Paths
## Question (Medium)
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

## Solution

class Solution {
public:
    int uniquePaths(int m, int n) {
        int**dp = new int*[m+2];
        for(int i=0; i<=m; i++)
            dp[i] = new int[n+2]{};
        
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(i==1 && j==1)
                    dp[i][j] = 1;
                else
                    dp[i][j]  = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m][n];
    }
};

## Notes:
* 建立一個2-d dp table。dp[i][j]表示到這個座標有**幾種走法**。
* 因為這個機器人只會往右和往下，所以可以推出dp[i][j] = dp[i-1][j] + dp[i][j-1]。(**左邊來的**+**上面來的**)
* 因為不想額外判斷邊界的部分，所以宣告dp[m+2][n+2]。

---
# 1143. Longest Common Subsequence
## Question (Medium)
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
## Solution (C++)

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int r = text1.length();
        int c = text2.length();
        int** dp = new int*[r+1];
        int maxima = INT_MIN;
        for(int i=0;i<=r; i++)
            dp[i] = new int[c+1]{};
        
        for(int i=r-1; i>=0; i--){
            for(int j=c-1; j>=0; j--){
                if(text1[i] == text2[j]){
                    dp[i][j] = 1 + dp[i+1][j+1];
                }
                else{
                    dp[i][j] = max(dp[i][j+1], dp[i+1][j]);
                }
                if(dp[i][j] > maxima)
                    maxima = dp[i][j];
            }
        }
        return maxima;
    }
};

## Notes
* dp[i][j]表示text1的第i個index開頭，和text2第j個index開頭的LCS長度。
* 若text1[i] == text2[j]表示兩個字串都有這個char，可以將問題再切分成dp[i+1][j+1]的子問題 (line 14)。
* 若text1[i]!=text2[j]，就有兩條路走，分別是dp[i+1][j]、dp[i][j+1]。
* 為了方便邏輯的撰寫，dp table有加上padding。
---