DP Ideas

• DP States - Cheatsheet
• dp[i] = Best result starting/ending at i position amongst all solutions
• must include the i position in solution --> Kadane
• dp[l][r] = for operations in subarray A[l..r] 
• Perform some operation on two sequences A[i..n] and B[j..n] --> like LCS
• dp[i][mask] = for array with bitmask

• Can decrease complexity by solving recurrence relation
• OBSERVE 
• f(i, k) = f(i+1, k-0) + f(i+1, k-1) + ... + f(i+1, k-(i-1))
• f(i, k-1) = f(i+1, k-1) + f(i+1, k-2) + ... + f(i+1, k-(i-1)) + f(i+1, k-i)
• Finally, f(i, k) = f(i, k-1) + f(i+1, k-0) - f(i+1, k-i)

Good Practices 

• use (~dp[i]) instead of (dp[i] != -1)
• use ans/ tmp instead of dp[ind][states] bcz can be long and hectic
• return dp[i] = ans => assigns and returns at the same time
• If string acts as state --> NEVER pass by reference
• bcz if value changes at address --> affect other previously stored values
• use int as return type
• NOT bool => bcz 3 dp values --> -1, 0, +1 and also -1 acts as true
• NOT void => bcz total optimal value get distorted => wrong answer
• int fun(int a=6){return a;} ---> fun() => gives 6 and fun(334) => gives 334
• called function with default arguments

Patterns

1. Kadane --> maximum sum of subarray
2. Longest Increasing Subsequence --> O(n logn)
• find max value of dp satisfying that pattern previously
  
  
3. Longest Common Subsequence --> O(n²)
4. Knapsack --> 2 cases whether take the current element or not
5. Reconstruction --> Eg.- Print all Longest Increasing Subsequence
• Just maintain parent array at every decision step
6. Bitmask DP - If n<30 → can use 2^30 if check is like YES / NO
• Can use bitset also --> better
  
  
7. Try all possibility → use for loop and iterate dp over each stuff [better to do iterative] => Apply only if sbko lena must hai else use knapsack (take or not take)
8. Digit dp → do from 0 to a => if in range [a, b] --> (0 to b) - (0 to a-1)
• Convert number to string using to_string(num)
• Digit DP

If going top to bottom => state def. ->transition ->base case ->memoization

If going bottom to top => memoization ->state def. ->base case ->transition

** If use for loop inside recursion, then time gets multiplied 
eg.- we have dp[n] and in recursion we have a for loop from 0 to n   --> overall time complexity = O(n²) --> SEE TIME COMPLEXITY (blog)**

If getting overcount => see if possibilities are overlapping or not

MISTAKES

• Find no. of ways to get sum 10 from [5, 5, 5] → changing - sum, no. of ways, index
  → state definition = dp[i][s] → no. of ways to get sum = s till index = i
• If less states → gets error → Hence, Time Complexity = O(sum * n)
• if (v[ind] != -1)

      {

          return v[ind];

      }

      v[ind] = sum(arr, ind + 1, a - arr[ind], v); --> let's say is a

      v[ind] = mod_add(sum(arr, ind + 1, a, v), v[ind]); --> Also returns a only bcz our v[ind+1] has been calculated


• Can we get sum 10 from [5, 5, 5] --> changing - sum, index, result
  --> state definition = dp[i][s] --> can we get sum = s till index = i
• Max. profit from [5, 5, 5] -> changing profit, index 
  --> state definition = dp[i] --> max. profit index = i
  
  
• If stuck in recursive way --> means state can give TLE / can't control the flow of recursion to update / constraints are strict --> FOLLOW iterative way using bottom to top
• For iterative use the fact that if know i --> how will it affect i+x 
  
  
• Count ways to write N as sum of given numbers
  CASE - I => If order matters -> AAB, ABA are different => normal 
  CASE - II => If ordering doesn't matter --> ABA, AAB are same
  => to AVOID repetitions ---> USE discrete maths trick 
  store in lexicographically smallest way to avoid repetition
  like dp[i][j] --> index at i with the [last element of seq. <= j]