LeetCode 75 - Dynamic Programming

1~3 개월의 준비 기간을 가지고 풀기에 좋은 문제들을 가지고 있는 특징이 있다.
이번 내용은 Dynamic Programming 주제다.

---

Min Cost Climbing Stairs
link : https://leetcode.com/problems/min-cost-climbing-stairs/description/?envType=study-plan-v2&envId=leetcode-75

/*
Patterns: 
Minimum (Maximum) Path to Reach a Target

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.
*/

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()); 
        dp[0] = cost[0]; 
        dp[1] = cost[1]; 
        for(int i = 2; i < cost.size(); i++){
            //dp[i] = min(dp[i-1], dp[i-2]) + (i == cost.size()-1 ? 0 : cost[i]); ]
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]; 
        }
        return min(dp[cost.size()-1], dp[cost.size()-2]); 
    }
};

House Robber
link : https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=leetcode-75

/*
Decision Making

The general problem statement for this pattern is forgiven situation decide whether to use or not to use the current state. 
So, the problem requires you to make a decision at a current state.

Statement
Given a set of values find an answer with an option to choose or ignore the current value.

Approach
If you decide to choose the current value use the previous result where the value was ignored; vice-versa, 
if you decide to ignore the current value use previous result where value was used.

*/ 

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

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

        return dp[nums.size()-1]; 
    }
};

Domino and Tromino Tiling
link : https://leetcode.com/problems/domino-and-tromino-tiling/submissions/1303961783/?envType=study-plan-v2&envId=leetcode-75

/*
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 numTilings(int n) {
        int MOD = 1'000'000'007;
        if(n <= 2){
            return n; 
        }

        long full[1001]; 
        long part[1001]; 

        full[1] = 1; 
        full[2] = 2; 
        part[2] = 1; 

        for(int i = 3; i < n + 1; ++i){
            full[i] = (full[i-1] + full[i-2] + 2 * part[i - 1]) % MOD; 
            part[i] = (part[i-1] + full[i - 2]) % MOD; 
        }

        return full[n]; 
    }
};

---

복습 필요한 문제

1. Domino and Tromino Tiling : 어려웠다. 생각하기 너무 힘들었을듯하다.