guest@cp-base:~/home$

Dynamic Programming

(3)

Dynamic programming patterns and optimizations

$ls dp/|wc -l3 templates found
template_kadane.cpp

Kadane's Algorithm

[Dynamic Programming]

Maximum contiguous subarray sum in O(n) time using linear DP.

#kadane#maximum-subarray#dp+1
$ cat kadane
template_digit-dp.cpp

Digit DP

[Dynamic Programming]

Count numbers in [L, R] satisfying digit-level constraints using memoized recursion.

#digit-dp#dp#counting+1
$ cat digit-dp
template_convex-hull-trick.cpp

Convex Hull Trick (Li Chao Tree)

[Dynamic Programming]

Dynamic line container with O(log C) insert and min query using Li Chao segment tree.

#convex-hull-trick#cht#li-chao+2
$ cat convex-hul..