Dynamic Programming compilation

 DYNAMIC PROGRAMMING COMPILATION

Basic Recurrence Relation (Fibonacci type)

1. Domino and Tromino tiling 
   
2. 552. Student Attendance Record II 
   
3. Dice Combinations (CSES) 
   
4. 1269. Number of Ways to Stay in the Same Place After Some Steps 
   
5. 
   

a[i+1] constrained on a[i] (=> f[n][d], a[i] taking values 0 to d-1)

1. 1220. Count Vowels Permutation 
   
2. 935. Knight Dialer 
   
3. Vacation (Atcoder) 
   
4. Array Description (CSES)
   
5. 
   

   DP on INTERVALS

Standard questions -> 

• Matrix Chain multiplication 
• RNA Secondary structure using base pair maximization

 dp[i][j] = max(dp[i][t] + dp[t+1][j] + f(i, t, j)) for all i <= t < j

1. Rectangle cutting (CSES)
2. 1039. Minimum Score Triangulation of Polygon 
3. 1130. Minimum Cost Tree From Leaf Values
   
4. 312. Burst Balloons 
   
5. 
   

DP on strings -> LCS Type

Choice of selection from an array (Knapsack type)

dp[j] = max(wj + dp[i], dp[j-1]) -> OBSERVE THAT FOR ALL IS NOT WRITTEN HERE, SO O(N)

1.  Maximum profit in Job Scheduling 
2. Maximum Earnings From Taxi 
3.   
4.   
5.   

Multiple choice of selection (Segmented least square type)

dp[j] = min(dp[j], Cij + dp[i]) for all 1 <= i <= j 

1.  132. Palindrome Partitioning II 
2.