Introduction to Dynamic Programming – Understanding DP Concepts

Day 25: Introduction to Dynamic Programming – Understanding DP Concepts

Dynamic Programming (DP) is a technique used to solve problems by breaking them down into smaller subproblems and storing the results of these subproblems to avoid redundant calculations.

Fibonacci Sequence in Java using DP

Recursive Fibonacci:

javaCopy codepublic class Fibonacci {
    public static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci of 5: " + fib(5));
    }
}

Dynamic Programming Fibonacci:

javaCopy codepublic class Fibonacci {
    public static 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];
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci of 5: " + fib(5));
    }
}