DP State Design

Most DP failures are state-design failures. Before code, write one sentence: dp[state] means exactly this. If that sentence is vague, the implementation will be fragile.

State, Transition, Answer

State captures the subproblem. Transition describes how smaller answers combine. Base cases stop the recurrence. Answer extraction says which state or aggregate gives the final product answer.

Scenario: Campaign Budget Allocation

A growth team chooses campaigns under a budget. Each campaign has cost and expected value. The state can be (campaignIndex, remainingBudget). The transition chooses skip or take. The base case is no campaigns or no budget.

Same Pattern in Java, Python, and JavaScript

0/1 knapsack is the classic state-design exercise: each item is either skipped or taken once.

class Knapsack {
    static int bestValue(int[] cost, int[] value, int budget) {
        int n = cost.length;
        int[][] dp = new int[n + 1][budget + 1];
        for (int i = 1; i <= n; i++) {
            for (int b = 0; b <= budget; b++) {
                dp[i][b] = dp[i - 1][b];
                if (cost[i - 1] <= b) {
                    dp[i][b] = Math.max(dp[i][b], dp[i - 1][b - cost[i - 1]] + value[i - 1]);
                }
            }
        }
        return dp[n][budget];
    }
}

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Maximize value under budget where each item can be used at most once.
• Return whether nums can be split into two subsets with equal sum.
• Count ways to assign + or - signs to reach target.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class Knapsack {
    static int bestValue(int[] cost, int[] value, int budget) {
        int n = cost.length;
        int[][] dp = new int[n + 1][budget + 1];
        for (int i = 1; i <= n; i++) {
            for (int b = 0; b <= budget; b++) {
                dp[i][b] = dp[i - 1][b];
                if (cost[i - 1] <= b) {
                    dp[i][b] = Math.max(dp[i][b], dp[i - 1][b - cost[i - 1]] + value[i - 1]);
                }
            }
        }
        return dp[n][budget];
    }
}

class Partition { static boolean can(int[] nums) { int sum=0; for(int x:nums) sum+=x; if(sum%2==1) return false; int target=sum/2; boolean[] dp=new boolean[target+1]; dp[0]=true; for(int x:nums) for(int s=target;s>=x;s--) dp[s]|=dp[s-x]; return dp[target]; } }

import java.util.*;
class TargetSum { static int ways(int[] nums,int target){ return dfs(nums,0,0,target,new HashMap<>()); } static int dfs(int[] a,int i,int sum,int t,Map<String,Integer> memo){ if(i==a.length) return sum==t?1:0; String k=i+":"+sum; if(memo.containsKey(k)) return memo.get(k); int ans=dfs(a,i+1,sum+a[i],t,memo)+dfs(a,i+1,sum-a[i],t,memo); memo.put(k,ans); return ans; } }

Solved modelWorked Interview Answer

Solve 0/1 knapsack by defining dp[i][budget]. The state uses item prefix and remaining budget. The transition compares skipping the item with taking it once if budget allows.

class Knapsack {
    static int bestValue(int[] cost, int[] value, int budget) {
        int n = cost.length;
        int[][] dp = new int[n + 1][budget + 1];
        for (int i = 1; i <= n; i++) {
            for (int b = 0; b <= budget; b++) {
                dp[i][b] = dp[i - 1][b];
                if (cost[i - 1] <= b) {
                    dp[i][b] = Math.max(dp[i][b], dp[i - 1][b - cost[i - 1]] + value[i - 1]);
                }
            }
        }
        return dp[n][budget];
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Using too much history in state.
• Using too little state and losing constraints.
• Wrong base cases.
• Reading current row when previous row is required.
• Returning the wrong cell.

Execution guardrailQuick-Start Checklist

• Write dp meaning.
• List state dimensions.
• Write transition.
• Set base cases.
• Choose fill order.
• Extract answer.
• State O(states * transition).

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice knapsack, subset sum, and target sum.
• Write state definitions before code.
• Study state compression after 2D correctness.