Leetcode 150, Leetcode 75, Top Liked 100 에 있는 DP 문제를 전부 연습한다

---

Leetcode 150

1D DP

Climbing Stairs
link : https://leetcode.com/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-interview-150

/*
Distinct Ways

Statement
Given a target find a number of distinct ways to reach the target.

Approach
Sum all possible ways to reach the current state.

routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]

*/


class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return 1; 
        if(n == 2) return 2; 

        vector<int> dp(n+1);
        dp[1] = 1; 
        dp[2] = 2; 

        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2]; 
        }
        return dp[n]; 
    }
};

---

Longest Increasing Subsequence
link : https://leetcode.com/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-interview-150

/*
Statement
Given a target find a number of distinct ways to reach the target.

Approach
Sum all possible ways to reach the current state.

routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]
Generate sum for all values in the target and return the value for the target.

*/

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


        return answer; 
    }
};

---

Coin Change
link : https://leetcode.com/problems/coin-change/?envType=study-plan-v2&envId=top-interview-150

/*
Statement
Given a target find minimum (maximum) cost / path / sum to reach the target.

Approach
Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.

routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

*/

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1); 
        dp[0] = 0; 
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.size(); j++){
                if(coins[j] <= i){ //지금 코인을 사용할것이다
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1); //남는 액수 
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount]; 
    }
};

---

Word Break
link : https://leetcode.com/problems/word-break/?envType=study-plan-v2&envId=top-interview-150

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(string& word : wordDict){
                if(i < word.length() -1) continue; 
                if(i == word.length()-1 || dp[i - word.length()]){
                    if(s.substr(i - word.length() + 1, word.length()) == word){
                        dp[i] = true; 
                        break; 
                    }
                }
            }
        }

        return dp[s.length()-1]; 

    }
};

---

Multidimentsional DP

---

복습 필요한 문제 :

1. Word Break : DP 방식으로 내가 만들 수 있는 범위까지 계속해서 Check 해주는게 인상적이었다. 다만 다시 풀라고 하면은 못풀거같아서 계속 리뷰가 필요할거같다.