22/06/29 longest increasing subsequence
기억하고자 하는 상태변수를 i, prev 로 현재 인덱스와 직전에 선택한 인덱스의 페어로 설정했다.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # prev: previous index
        def go(i, prev, m):
            key = i, prev
            N = len(nums)
            if i==N: return 0
            if key in m: return m[key]
            
            # not take
            not_take=go(i+1, prev, m)
            
            # take
            take=0
            if prev<0 or nums[prev] < nums[i]:
                take=1+go(i+1, i, m)
            ans = max(not_take, take)
            m[key] = ans
            return ans

        ans = go(0, -10**4, {})
        return ans

22/06/27 house lobber
패턴: Decision Making

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.

for (int i = 1; i < n; ++i) {
   dp[i][1] = max(dp[i-1][0] + nums[i], dp[i-1][1]);
   dp[i][0] = dp[i-1][1];
}

22/06/24 longest increasing subsequence (by binary search)
nums 를 순회하면서 결과배열에 정렬된 상태로 하니씩 삽입. index 가 배열의 끝을 가리키면 추가하고 그렇지 않으면 덮어쓰기.

예: nums=[1,3,2], r=[]
i=0 r=[1]
i=1 r=[1,3]
i=2 r=[2,3]
결과배열 r 은 longest increasing subsequence 와 같은 길이임을 보장한다. why?

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        result = []
        for i in nums:
            j = bisect.bisect_left(result,i)
            if j == len(result):
                result.append(i)
            else:
                result[j] = i
        return len(result)

22/06/23 coin change (DP top down)
유형: Minimum(Maximum) Path to Reach a Target

MAX = 10**5
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def go(amount, memo):
            if amount==0: return 0
            if amount<0: return MAX
            
            if amount in memo: return memo[amount]
            
            xs = []
            for c in coins:
                xs.append(1 + go(amount - c, memo))
            
            ans = min(xs)
            memo[amount] = ans
            return ans
        
        ans = go(amount, {})
        return ans if ans < MAX else -1

재귀 호출을 모든 코인에 대해 탐색하면서 amount 를 상태변수로 두고 cache 하기.

22/06/21 coin change
DP점화식을 적용하여 amount 를 1부터 차례로 증가시키면서 목표 amount 까지 계산한다.
질문: DP점화식이 가능하면 DP memoization 도 가능한가? DP memoization 은 아직 해결책을 찾지 못함.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def go(amount):
            DP = [None for _ in range(amount+1)]
            DP[0] = 0
            
            for i in range(1,amount+1):
                xs = [DP[i-c] + 1 for c in coins if i-c>=0 and DP[i-c] != None]
                if xs != []:
                    DP[i] = min(xs)
                else:
                    DP[i] = None
                                
            return DP[amount]
        y = go(amount) 
        
        return y if y != None else -1

22/06/20 longest increasing subsequence

DP없이 recursion 으로 표현한 모습. 본래 문제인 nums 가 더 작은 문제의 조합으로 표현.
max(1+go(..), go(..), go(..))

optimal substructure 와 overlapping subprobles 특징이 있다면 DP 적용가능.

breaking it down into simpler sub-problems in a recursive manner ..
and then recursively finding the optimal solutions to the sub-problems

then it is said to have optimal substructure.

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead.[1] This is why merge sort and quick sort are not classified as dynamic programming problems.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:

        # naive recursion
        def go(i, prev):
            if i==len(nums): return 0
                
            now = nums[i]

            ans = max(
                # accept
                1 + go(i+1, now) if prev < now else 0,
                
                # skip-continue
                go(i+1, prev),
                
                # reset
                go(i+1, now)
            )
            return ans
 

DP 를 적용해보자.

https://leetcode.com/discuss/general-discussion/458695/Dynamic-Programming-Patterns

TODO

분류하기
https://leetcode.com/problems/longest-string-chain/
https://leetcode.com/problems/longest-increasing-subsequence/ (Maxiumum path to reach a target?)

patterns

• Minimum(Maximum) Path to Reach a Target
• Distinct Ways
• Merging Intervals
• DP on Strings
• Decision Making

Minimum(Maximum) Path to Reach a Target

problem list: https://leetcode.com/list/55ac4kuc

Generate problem statement for this pattern

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]
Generate optimal solutions for all values in the target and return the value for the target.

Top-Down

for (int j = 0; j < ways.size(); ++j) {
    result = min(result, topDown(target - ways[j]) + cost/ path / sum);
}
return memo[/*state parameters*/] = result;

Bottom-Up

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] = min(dp[i], dp[i - ways[j]] + cost / path / sum) ;
       }
   }
}
 
return dp[target]

1. Minimum Path Sum
2. Triangle (solved)
3. Dungeon Game
4. Maximal Square
5. Perfect Squares
   6. Coin Change
6. Ones and Zeroes
7. 2 Keys Keyboard
   9. Min Cost Climbing Stairs
8. Minimum Number of Refueling Stops
9. Minimum Falling Path Sum
10. Minimum Cost For Tickets
11. Last Stone Weight II
12. Tiling a Rectangle with the Fewest Squares

Distinct Ways

problem list: https://leetcode.com/list/55ajm50i

Generate problem statement for this pattern

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]

Top-Down

for (int j = 0; j < ways.size(); ++j) {
    result += topDown(target - ways[j]);
}
return memo[/*state parameters*/] = result;

Bottom-Up

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] += dp[i - ways[j]];
       }
   }
}
 
return dp[target]

1. Unique Paths
2. Unique Paths II
3. Climbing Stairs
4. Combination Sum IV
5. Partition Equal Subset Sum
6. Target Sum
7. Out of Boundary Paths
   8. Number of Longest Increasing Subsequence
8. Knight Probability in Chessboard
9. Domino and Tromino Tiling
10. Minimum Swaps To Make Sequences Increasing
11. Soup Servings
12. Knight Dialer
13. Number of Dice Rolls With Target Sum
14. Count Vowels Permutation
15. Dice Roll Simulation
16. Number of Ways to Stay in the Same Place After Some Steps

Mergint Intervals

Problem List: https://leetcode.com/list/55aj8s16

1. Unique Binary Search Trees
2. Burst Balloons
3. Guess Number Higher or Lower II
4. Remove Boxes
5. Minimum Cost to Merge Stones
6. Minimum Score Triangulation of Polygon
7. Minimum Cost Tree From Leaf Values

DP on Strings

Problem List: https://leetcode.com/list/55afh7m7

Statement

Given two strings s1 and s2, return some result

Approach

Most of the problems on this pattern requires a solution that can be accepted in O(n^2) complexity.

1. Longest Palindromic Substring
2. Edit Distance
3. Distinct Subsequences
4. Longest Palindromic Subsequence
5. Palindromic Substrings
6. Minimum ASCII Delete Sum for Two Strings
7. Shortest Common Supersequence
   8. Longest Common Subsequence

Decision Making

Problem List: https://leetcode.com/list/55af7bu7

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.

1. Best Time to Buy and Sell Stock
2. Best Time to Buy and Sell Stock III
3. Best Time to Buy and Sell Stock IV
4. House Robber
5. Best Time to Buy and Sell Stock with Cooldown
6. Best Time to Buy and Sell Stock with Transaction Fee