Dynamic programming in Java

Common Java DP problems

• Climbing Stairs
• House Robber
• Coin Change
• Longest Increasing Subsequence
• Unique Paths
• Partition Equal Subset Sum
• Edit Distance

Example: Fibonacci DP

int fib(int n) {
    int[] dp = new int[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];
}

Interview guidance

DP is usually the answer when the same subproblem repeats.