Dynamic Programming Notes

Categorization

Maximum Path
Longest Ascending Subsequence
Leetcode 152. Maximum Product Subarray https://leetcode.com/problems/maximum-product-subarray/

Usually given an array/sequence or grid/matrix as your input
Need to find a subsequence/vector/path for
- maximizing/minimizing a certain property
- counting
- true/false
State is represented by dp[i] and dp[i][j], which are the most optimal cases for a[i] or a[i][j]
Initalization is usually dp[0] with a[0]

Path:
- Leetcode 62. Unique Paths https://leetcode.com/problems/unique-paths/
- Leetcode 63. Unique Paths II https://leetcode.com/problems/unique-paths-ii/
- Leetcode 64. Minimum Path Sum https://leetcode.com/problems/minimum-path-sum/
- Leetcode 931. Minimum Falling Path Sum
Sequence:
- Leetcode 674. Longest Continuous Increasing Subsequence https://leetcode.com/problems/longest-continuous-increasing-subsequence/
Matrix:
- Leetcode 1277. Count Square Submatrices with All Ones
- Leetcode 221. Maximal Square
- Leetcode 361. Bomb Enemy

When make a decision for last step, it relies on the state of previous step
dp[i] and dp[i][j] are not sufficient, usually need to save more state
When initializing, usually add dp[0] dp[0][j] for empty sequence
- hence the length of dp[] or dp[][] is usually n+1
dp[i] and dp[i][j] is usually representing the optimal solution from index 0 to index (i-1) in the input array/matrix
- Whereas in coordinate-based, dp[i] and dp[i][j], index i and (i,j) are simply used to represent the optimal solution for index i and (i,j) in the input array/matrix
Leetcode 198. House Robber https://leetcode.com/problems/house-robber/
Leetcode 213. House Robber II https://leetcode.com/problems/house-robber-ii/
Leetcode 256. Paint House https://leetcode.com/problems/paint-house
Leetcode 265. Paint House II https://leetcode.com/problems/paint-house-ii/
Leetcode 121. Best Time to Buy and Sell Stock https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Leetcode 122. Best Time to Buy and Sell Stock II https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
Leetcode 123. Best Time to Buy and Sell Stock III https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
Leetcode 188. Best Time to Buy and Sell Stock IV https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/