DP Patterns Every CP Solver Should Know

Dynamic programming has a reputation for being the hardest topic in competitive programming. I used to agree with that. Then I realised something: most DP problems aren't unique. They're variations on about six core patterns. Once you internalise those patterns, you stop treating each DP problem as a new puzzle and start asking: "which pattern is this?" This post breaks down the six patterns I keep coming back to. For each one, I'll explain the core idea, show a simple example in C++, and point you to a representative problem to practice. Pattern 1: Linear DP (1D State) Core idea: The answer for position i depends only on answers at earlier positions. This is the most foundational pattern — the building block everything else extends from. Classic example: Longest Increasing Subsequence int lis ( vector < int >& a ) { int n = a . size (); vector < int > dp ( n , 1 ); for ( int i = 1 ; i < n ; i ++ ) for ( int j = 0 ; j < i ; j ++ ) if ( a [ j ] < a [ i ]) dp [ i ] = max ( dp [ i ], dp [