Fibonacci DP

Easy

Python

def fib(n):
    if n<=1: return n
    dp=[0]*(n+1); dp[1]=1
    for i in range(2,n+1): dp[i]=dp[i-1]+dp[i-2]
    return dp[n]

Java

public int fib(int n){
    if(n<=1) return n;
    int[] dp=new int[n+1]; dp[1]=1;
    for(int i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
    return dp[n];
}

Key Insight

[0]*(n+1) vs new int[n+1]. Java int arrays default to 0.

Python → Java Differences

[0]*(n+1) vs new int[n+1]
Java int[] defaults to 0
DP transition identical

Python

def fib(n):
    if n<=1: return n
    dp=[0]*(n+1); dp[1]=1
    for i in range(2,n+1): dp[i]=dp[i-1]+dp[i-2]
    return dp[n]

Java

public int fib(int n){
    if(n<=1) return n;
    int[] dp=new int[n+1]; dp[1]=1;
    for(int i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
    return dp[n];
}

Algorithm Steps

1. Base cases
2. Build up from smaller

All Dynamic Programming Next →