Freaks City

Overview Linear dynamic programming is one of the most fundamental types of DP problems. Instead of a lengthy introduction, the key is to solve many problems to develop intuition. Basic Steps State Definition: Define dp[i] as the optimal solution (maximum, minimum, count of ways, etc.) for the first i elements. State Transition: Derive the cur ...

Consider a sequence $A = (a_1, a_2, \dots, a_n)$. We want to partition $A$ into contiguous subsequences, and then arrange these subsequences to form a new sequence $f_1, f_2, \dots, f_k$. Each contiguous subsequence $f_1, \dots, f_p$ must satisfy either $f_1 \le f_2 \le \dots \le f_p$ or $f_1 \ge f_2 \ge \dots \ge f_p$. The cost associated with ...