DP is efficient and provide O(n) operation without recursion.
It requires state transition equation to be identified (from n-2, n-1 to n)
as well as correct base case (n=0, n=1).
It's like Math induction.
It's often applied to combinatorics problem asking for total number.
DP has 1-DP, one dimension and 2-DP, two dimension transfer function.
Typical 1-D DP examples are
climb stairs
max subArray
paint fence
Typical 2-D examples are
MinimumPathSum
Unique path for robots
Paint house
Famous ones are Edit Distance
Word Break
没有评论:
发表评论