Dynamic Programming (Part1)

<LeetCode 문제들>

- climbing stairs

-coin change

- longest incresing subsequence

- word break

=====================================================================

DP 는 결국 Optimal Substructure를 구하는 것

1. DFS + Memoization

2. Recursion + caching

​

문제 푸는 순서

1. count the parameters : dimensionally 생각해보기

​

2. Identify the base case

​

3. Implementing memoization / tabulation

dp문제는 iterative or recursive 둘 중 하나로 무조건 풀리게 되어 있따.

- iterative = bottom-up -> tabulation

- recursive = top -down -> memoization

​

4. 이렇게 나오는 과정을 save해야 함

-> 결국 배열, 리스트가 필요

​

​

1. Climbing Stairs

<먼저, recursive way>

->

1. 값을 계속 담을 배열 만들기

2. base case에 대한 값

3. 값이 담겨있다고 하면, 계산할 필요 없음

4. 다음 값 구하고 배열에 담기

​

<iterative way>

훨씬 간단하네....

​

2. Coin Change

​

3. Longest Incresing Subsequence

4. Word Break

답은 뭐든 간에 배열 맨 마지막 것..ㅋㅋㅋ 그리고 dp[0]에 ""를 넣어주었기 때문에 -1하지 않아도 됨!!

f[j]=> dp[j]

f[i] => dp[i]로 변경해야 합니다.

​

*** recurrence relation을 생각해내는 게 중요합니다!!! ( 점화식)