Leet Code - Dynamic Programming
Optimisation
Optimisation DP resolves the solution top down, using stored values to reduce execution space and reuse past computed values.
Generative
Generative DP generates the solution from the ground up, using incrementally built values.
Maximum Fee Collection
Input: 3 1 2 4 // size of batch 0.1 0.15 0.2 0.3 // fee 4 // max size
(ignore the tab)
Output 0.35 // max fee for max size -> 1 + 2
Assumptions:
- Size of batch is not unique
- Fee is not unique even within the same size
Solution:
DP stored: dp[max_size + 1][len(sizes)]
row: max size col: after index is included content: max fee
Example 0 1 2 3 0 0 0 0 0 1 0 0.15 0.15 0.15 2 0 0.15 0.2 0.2 3 0.1 0.15 0.35 0.35 4 0.1 0.25 0.35 0.35
Explanation example:
For index j, max size i if j - 1 < 0 -> if i >= current_size -> use current_fee else use 0 if i - current_size < 0 -> use dp[i][j-1] else size_including_current = current_fee + dp[i - current_size][j - 1] if size_including_current > dp[i][j-1] -> use size_including_current else use dp[i][j-1]
max is dp[max_size][len(sizes) - 1]