Dynamic programming is a method for solving problems by breaking them down into smaller subproblems and storing their solutions. The approach is to build a table of solutions for smaller subproblems and use them to build the solution for the original problem. The basic idea behind dynamic programming is to avoid repetitive calculations by storing the solutions to subproblems and reusing them whenever necessary.
Dynamic programming can be used to solve both optimization and counting problems, where the goal is to minimize or maximize a certain value, or to count the number of solutions to a problem. It is particularly useful when dealing with problems where the solution can be decomposed into overlapping subproblems.
Dynamic programming is a powerful technique in competitive programming as it can be used to solve problems with exponential time complexity and make them solvable in polynomial time.
Example 1: Fibonacci Numbers The problem of finding the n-th Fibonacci number can be solved using dynamic programming. The naive approach to this problem is to compute each Fibonacci number from scratch, which leads to a time complexity of O(2^n).
However, by using dynamic programming, we can store the solutions to subproblems and reuse them whenever necessary. The approach is to build a table that stores the Fibonacci numbers from 0 to n and use them to build the solution for the n-th Fibonacci number.
int fib(int n) {
int f[n+1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
Example 2: Longest Increasing Subsequence The problem of finding the longest increasing subsequence in an array can be solved using dynamic programming. The approach is to build a table of solutions for subproblems and use them to build the solution for the original problem.
The table dp stores the length of the longest increasing subsequence ending at index i. The value of dp[i] is obtained by comparing dp[j] for all j < i and a[j] < a[i]. The final result is the maximum value in the dp table.
int LIS(int arr[], int n) {
int dp[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
}
int max = 0;
for (int i = 0; i < n; i++) {
if (max < dp[i]) {
max = dp[i];
}
}
return max;
}
Dynamic programming can be applied to a wide range of problems in computer science, from simple problems like finding the n-th Fibonacci number, to more complex problems like finding the shortest path in a graph or solving the knapsack problem. To be successful with dynamic programming, it is important tounderstand the problem first, identify the overlapping subproblems and figure out how to solve the problem using those subproblems.
Divide and Conquer: Dividing the problem into smaller subproblems and solve each subproblem. Store the results of each subproblem so that it can be reused later.
Memoization: Store the solutions to the subproblems in an array, hash table or any other data structure so that it can be reused later instead of solving it again.
Constructing a Solution: With the results of subproblems, you can now construct the solution to the main problem.
Optimal Substructure: The solution to the main problem depends on the solutions of the subproblems, so it's important to have an optimal solution to the subproblems.
Overlapping Subproblems: The same subproblems should be solved multiple times, so it's important to find a way to reuse the solutions of the subproblems instead of solving it again.
Bottom-Up or Top-Down Approach: There are two approaches to solving dynamic programming problems, bottom-up or top-down approach. Bottom-up approach solves the subproblems first and then construct the solution, while the top-down approach first constructs the solution and then solves the subproblems if needed.
Example: Fibonacci sequence problem can be solved using dynamic programming. The subproblems are finding the nth Fibonacci number. The solution to the nth Fibonacci number depends on the solutions of the (n-1)th and (n-2)th Fibonacci numbers. With the bottom-up approach, you can store the solutions of the subproblems in an array and reuse them later instead of solving it again.
