Dynamic Programming

Concept

Definition

• Dynamic programming is a powerful technique for solving complex problems by breaking them down into smaller subproblems. This approach allows for the optimization of computational resources by avoiding redundant calculations and ensuring that each subproblem is only solved once.

• DP = recursion + memoization.

• It is an optimization over recursion.

• Memoization: It involves storing the results of previously computed subproblems in a table or other data structure, to avoid having to recompute them in the future.

public static int fibonacci(int n) {
    // Declare an array to store the fibonacci numbers
    int[] fib = new int[n + 1];

    // Initialize the first two numbers in the sequence
    fib[0] = 0;
    fib[1] = 1;

    // Calculate the remaining fibonacci numbers
    for (int i = 2; i <= n; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }

    // Return the nth fibonacci number
    return fib[n];
  }

To dynamically solve a problem, these are the necessary conditions to check:

1. Overlapping Subproblems: When the solutions to the same subproblems are needed repetitively for solving the actual problem. The problem is said to have overlapping subproblems property.

2. Optimal Substructure Property: If the optimal solution of the given problem can be obtained by using optimal solutions of its subproblems then the problem is said to have Optimal Substructure Property.

Approaches

1. Bottom-Up Approach (Tabulation): In this approach, the problem is solved by starting from the smallest subproblems and gradually building up to larger and more complex solutions. This method is often used when the subproblems have overlapping solutions, as it allows for the efficient reuse of previously computed results.

   // Tabulated version to find factorial x.
   int dp[MAXN];
   
   // base case
   int dp[0] = 1;
   for (int i = 1; i< =n; i++)
   {
       dp[i] = dp[i-1] * i;
   }
   

2. Top-Down Approach (Memoization): In this approach, the problem is solved by starting from the largest, most complex subproblem and working downwards to smaller subproblems. This method is often used when the subproblems have distinct solutions and do not overlap, as it allows for a more efficient and concise solution.

   // initialized to -1
   int dp[MAXN]
   
   // return fact x!
   int solve(int x)
   {
       if (x==0)
           return 1;
       if (dp[x]!=-1)
           return dp[x];
       return (dp[x] = x * solve(x-1));
   }
   

   So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.

   Thank you, Have a nice day !!