DYNAMIC PROGRAMMING PROBLEM-SOLVING TRICKS

Essential Dynamic Programming Tricks

#	Trick	Description
1	Identify optimal substructure	Break problem into smaller subproblems with optimal solutions
2	Memoization (Top-down)	Store computed results to avoid redundant calculations
3	Tabulation (Bottom-up)	Build solution iteratively from base cases
4	State representation	Carefully choose what defines the state in your DP table
5	Space optimization	Reduce space complexity by reusing or compressing DP table
6	DP on strings	Use 2D tables for string comparison/edit distance problems
7	DP on trees	Apply DP with post-order traversal for tree problems
8	Knapsack variations	Recognize unbounded, 0/1, fractional knapsack patterns
9	DP with bitmasking	Use bitmask to represent subsets in state
10	DP on grids	Solve path-counting or min-path problems with grid traversal
11	Prefix/suffix DP	Build solutions based on prefixes or suffixes of input
12	DP with probability	Handle probabilistic outcomes in state transitions
13	DP with binary search	Combine DP with binary search for optimization
14	DP with segment trees	Use advanced data structures to optimize state queries
15	DP with convex hull trick	Optimize certain recurrence relations

Implementation Examples

Fibonacci with Memoization

// Top-down DP with memoization
#define MAX 100
int memo[MAX] = {0};

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

Fibonacci with Tabulation

// Bottom-up DP with tabulation
int fib(int n) {
    int dp[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

Grid DP Example

// Unique paths in grid (m x n)
int uniquePaths(int m, int n) {
    int dp[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0) 
                dp[i][j] = 1;
            else 
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

0/1 Knapsack Problem

// 0/1 Knapsack DP solution
int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (wt[i-1] <= w)
                dp[i][w] = fmax(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[n][W];
}