Discuss the concept of optimal substructure in dynamic programming with an example.?

Optimal substructure is a key concept in dynamic programming (DP) that describes the property of many problems where an optimal solution to the problem can be obtained by combining optimal solutions to its subproblems. It means that if we can solve the subproblems optimally, we can combine their solutions to solve the original problem optimally.

Let’s take an example of the Fibonacci sequence to understand this concept better. The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding numbers. It can be represented by the following recursive formula:

Fib(n) = Fib(n-1) + Fib(n-2), for n>=2
Fib(0) = 0, Fib(1) = 1

To calculate ‘Fib(n)‘, one way is to use recursion and compute ‘Fib(n-1)‘ and ‘Fib(n-2)‘ recursively to get the result. However, this approach can result in a lot of duplicate calculations, as the same subproblems may be solved multiple times.

Dynamic programming addresses this problem by breaking down the problem into smaller subproblems and solving each subproblem only once. The optimal substructure property of the Fibonacci sequence problem can be seen as follows,

The optimal solution to ‘Fib(n-1)‘ can be obtained by solving the subproblem, ‘Fib(n-2)‘ and ‘Fib(n-3)‘

The optimal solution to ‘Fib(n-2)‘ can be obtained by solving the subproblem, ‘Fib(n-3)‘ and ‘Fib(n-4)‘

...

The optimal solution to ‘Fib(2)‘ can be obtained by solving the subproblem, ‘Fib(1)‘ and ‘Fib(0)‘

Using this observation, we can avoid solving redundant subproblems and compute the value of the Fibonacci sequence using Dynamic Programming. Here’s the DP solution of the above problem using memoization technique in Java,

class Fibonacci{
    private int[] memo = new int[100];

    public int fib(int n){
        if (n == 0) return 0;
        if (n == 1) return 1;

        if (memo[n] != 0) {
            return memo[n];
        }

        int result = fib(n-1) + fib(n-2);

        memo[n] = result;

        return result;
    }
}

In this solution, we use an array ‘memo‘ to avoid recomputing the same subproblems. This approach significantly reduces the time complexity of the algorithm.

Thus, the concept of optimal substructure in dynamic programming enables us to efficiently solve complex problems by breaking them down into smaller subproblems and computing optimal solutions to these subproblems.