Dynamic Programming (DP) Patterns — DSA Pattern

The Dynamic Programming (DP) Patterns pattern applies when you need fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break. Its time complexity is O(n) to O(n³) depending on the number of DP dimensions and transitions and space complexity O(n) to O(n²), often reducible to O(1) with a rolling array. It is used in 45 problems on Thita, including Best Time to Buy and Sell Stock, Best Time to Buy and Sell Stock II and Best Time to Buy and Sell Stock III. Common variations are 1D Array (Word Break Style) and 2D Array (Edit Distance / Levenshtein Distance).

Master DP patterns including Fibonacci, Kadane, knapsack, LCS, LIS, edit distance, and grid paths. Solve optimization problems with overlapping subproblems.

Dynamic Programming (DP) Patterns is pattern 12 of 16 in the Thita.ai DSA course. It covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break, split into 12 subpatterns and about 5 hours of study. It is one of the interview-critical patterns, so it is worth covering before your first onsite.

Subpatterns of Dynamic Programming (DP) Patterns

Each subpattern below has its own theory page and problem set. They are listed in the order the course teaches them.

• 1D Array (Fibonacci Style) — Solve problems with Fibonacci-like recurrence: climbing stairs, house robber, decode ways. (core technique)
• 1D Array (Kadane's Algorithm for Max/Min Subarray) — Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time. (core technique)
• 1D Array (0/1 Knapsack Subset Sum Style) — Solve 0/1 knapsack, partition equal subset sum, and target sum problems. (core technique)
• 1D Array (Coin Change / Unbounded Knapsack Style) — Solve coin change and unbounded knapsack problems where items can be reused. (core technique)
• 1D Array (Word Break Style) — Determine if string can be segmented into dictionary words using DP. (important variation)
• 2D Array (Unique Paths on Grid) — Count paths and find optimal paths in grids using 2D dynamic programming. (core technique)
• 2D Array (Longest Common Subsequence - LCS) — Find longest common subsequence between two strings using 2D DP. (core technique)
• 2D Array (Edit Distance / Levenshtein Distance) — Calculate minimum edit operations to transform one string to another using 2D DP. (important variation)
• Longest Increasing Subsequence (LIS) — Find LIS using DP and binary search optimization. O(n log n) solution. (important variation)
• Stock problems — Solve stock trading problems with k transactions, cooldown, and transaction fees using DP. (depth topic)
• Catalan Numbers — Solve problems involving Catalan numbers: unique BSTs, parentheses combinations, polygon triangulation. (depth topic)
• Interval DP — Solve problems on intervals like burst balloons and matrix chain multiplication using interval DP. (depth topic)

How to practise Dynamic Programming (DP) Patterns on Thita.ai

Read the theory for a subpattern, then solve its problems in the browser editor. Your solution runs against the problem's test cases, and the AI coach gives a hint on the technique you are missing rather than the finished answer. Progress is tracked per subpattern, so the tracker shows which of the 12 Dynamic Programming (DP) Patterns subpatterns you have covered. Topics covered here include dynamic programming, DP patterns, memoization, tabulation, Fibonacci DP, Kadane algorithm, knapsack problem, longest common subsequence.

Related DSA patterns

• Greedy Patterns — Interval scheduling, jump games, stock trading, and task scheduling.
• Backtracking Patterns — Subsets, permutations, combinations, N-Queens, and word search.
• Graph Traversal Patterns (DFS & BFS) — DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST.
• Bit Manipulation Patterns — XOR tricks, counting bits, power-of-two checks, and Hamming weight.
• Design Patterns — Tries, LRU/LFU cache, and data structure design.
• All 16 DSA patterns
• The DSA patterns sheet
• Coding practice