# Dynamic Programming Patterns in LeetCodeAnimation: 6 Essential Techniques

> Master 6 essential dynamic programming patterns from LeetCodeAnimation. Learn memoization tabulation space optimization counting prefix string and interval DP techniques for LeetCode problems.

- Repository: [吴师兄学算法/LeetCodeAnimation](https://github.com/MisterBooo/LeetCodeAnimation)
- Tags: deep-dive
- Published: 2026-03-01

---

**The LeetCodeAnimation repository demonstrates six core dynamic programming patterns—top‑down memoization, bottom‑up tabulation, space‑optimized 1‑D arrays, counting ways, prefix string DP, and interval DP—that cover the majority of LeetCode DP problem archetypes.**

The **MisterBooo/LeetCodeAnimation** repository provides visual explanations and code implementations for classic LeetCode problems, with a strong focus on **dynamic programming patterns**. By analyzing the source articles and code snippets, we can identify six recurring DP architectures that serve as templates for solving everything from Fibonacci sequences to game theory challenges.

## Top‑Down Recursion with Memoization

This pattern uses a recursive function to solve sub‑problems and caches results to avoid redundant calculations, converting exponential time complexity to linear.

In [`1137-Tribonacci/Article/1137-Tribonacci.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/1137-Tribonacci/Article/1137-Tribonacci.md), the implementation stores computed values in an `int[] memo` array. The base cases handle `n == 0`, `n == 1`, and `n == 2`, while recursive calls populate the cache for larger values.

```java
int[] memo = new int[38];               // 0 → unknown, >0 → cached result
int tribonacci(int n) {
    if (memo[n] != 0) return memo[n];
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    memo[n] = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
    return memo[n];
}

```

## Bottom‑Up Tabulation Approaches

Bottom‑up DP builds solutions iteratively from base cases, eliminating recursion stack risks and often providing better cache locality.

### 2‑Dimensional DP Tables

For problems requiring two dimensions of state, the repository uses full matrices. In [`0120-Triangle/Article/0120-Triangle.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0120-Triangle/Article/0120-Triangle.md), the solution creates `int[][] dp = new int[n][n]` to store minimum path sums, filling from the bottom row upward.

```java
int minimumTotal(List<List<Integer>> tri) {
    int n = tri.size();
    int[][] dp = new int[n][n];
    // base – copy last row
    for (int i = 0; i < n; ++i) dp[n-1][i] = tri.get(n-1).get(i);
    // fill upwards
    for (int i = n-2; i >= 0; --i)
        for (int j = 0; j <= i; ++j)
            dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + tri.get(i).get(j);
    return dp[0][0];
}

```

### Space‑Optimized 1‑D Arrays

When only the previous row is needed, the repository collapses the table. The same Triangle article demonstrates converting the 2‑D solution to `int[] dp`, updating values in‑place to achieve **O(n)** space complexity.

```java
int minimumTotalOptimized(List<List<Integer>> tri) {
    int n = tri.size();
    int[] dp = new int[n];
    for (int i = 0; i < n; ++i) dp[i] = tri.get(n-1).get(i); // last row
    for (int i = n-2; i >= 0; --i)
        for (int j = 0; j <= i; ++j)
            dp[j] = Math.min(dp[j], dp[j+1]) + tri.get(i).get(j);
    return dp[0];
}

```

## Simple 1‑D DP for Counting Ways

For problems asking for the number of ways to reach a state, the repository uses linear recurrence relations with constant memory. In [`0070-Climbing-Stairs/Article/0070-Climbing-Stairs.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0070-Climbing-Stairs/Article/0070-Climbing-Stairs.md), the solution tracks only the two previous values to compute the Fibonacci‑like sequence.

```javascript
function climbStairs(n) {
    if (n <= 2) return n;
    let a = 1, b = 2;               // dp[1], dp[2]
    for (let i = 3; i <= n; ++i) {
        const c = a + b;            // dp[i] = dp[i‑1] + dp[i‑2]
        a = b;
        b = c;
    }
    return b;
}

```

## Prefix DP on Strings

String segmentation problems utilize boolean arrays where `dp[i]` indicates whether the prefix ending at position `i` can be formed. The implementation in [`0139-Word-Break/Article/0139-Word-Break.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0139-Word-Break/Article/0139-Word-Break.md) uses nested loops to check all possible cuts.

```java
boolean wordBreak(String s, Set<String> dict) {
    int n = s.length();
    boolean[] dp = new boolean[n+1];
    dp[0] = true;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < i; ++j)
            if (dp[j] && dict.contains(s.substring(j,i))) {
                dp[i] = true;
                break;
            }
    return dp[n];
}

```

## Interval DP for Game Theory

For problems involving optimal play on contiguous segments, the repository defines states on intervals. In `notes/LeetCode第877号问题：石子游戏.md`, the `dp(l, r)` state stores the maximum score difference a player can achieve over the opponent for the subarray `piles[l…r]`.

```java
int[] piles;               // global input
int[][] memo;              // memo[l][r] = max score for interval [l,r]

int dfs(int l, int r) {
    if (l > r) return 0;
    if (memo[l][r] != 0) return memo[l][r];
    // current player takes left or right pile
    int takeLeft  = piles[l] - dfs(l+1, r);
    int takeRight = piles[r] - dfs(l, r-1);
    memo[l][r] = Math.max(takeLeft, takeRight);
    return memo[l][r];
}

```

## Summary

- **Top‑down memoization** caches recursive results to convert exponential time to linear, as seen in the Tribonacci implementation.
- **Bottom‑up tabulation** builds solutions iteratively, using either **2‑D tables** for complex state transitions or **1‑D arrays** for space‑optimized solutions like the Triangle problem.
- **Counting ways** problems use simple linear recurrence with constant memory, exemplified by the Climbing Stairs solution.
- **Prefix DP** handles string segmentation by tracking valid prefix states, demonstrated in the Word Break implementation.
- **Interval DP** solves game theory and range problems by defining states on sub‑intervals, as shown in the Stone Game solution.

## Frequently Asked Questions

### What are the main dynamic programming patterns in LeetCodeAnimation?

The repository covers six primary patterns: **top‑down recursion with memoization**, **bottom‑up 2‑D tabulation**, **space‑optimized 1‑D bottom‑up**, **simple 1‑D counting ways**, **prefix DP for strings**, and **interval DP for game theory**. Each pattern targets specific problem structures found in LeetCode challenges.

### How does the repository optimize space in DP solutions?

The LeetCodeAnimation articles demonstrate **space optimization** by collapsing 2‑D tables into 1‑D arrays when only the previous row or state is needed. For example, the Triangle problem first implements a full `int[][] dp` matrix, then refactors to `int[] dp` to reduce memory from **O(n²)** to **O(n)**.

### Which pattern is best for string segmentation problems?

For string segmentation and dictionary word problems, the repository uses **prefix DP**. This pattern defines `dp[i]` as a boolean indicating whether the substring `s[0…i‑1]` can be segmented. The Word Break implementation in [`0139-Word-Break/Article/0139-Word-Break.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0139-Word-Break/Article/0139-Word-Break.md) uses nested loops to check all possible cuts, making this the standard approach for such problems.

### Where can I find interval DP examples in the repository?

Interval DP examples appear in game theory problems involving contiguous ranges. The **Stone Game** solution located at `notes/LeetCode第877号问题：石子游戏.md` implements `dp(l, r)` to represent the maximum score difference achievable on the subarray `piles[l…r]`. This file demonstrates how to handle optimal play scenarios using memoization over intervals.