Dynamic Programming
Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable when the subproblems are overlapping and can be stored for future use.
Common Dynamic Programming Problems
- Fibonacci Sequence: Finding the nth Fibonacci number using memoization.
- Knapsack Problem: Finding the maximum value that can be put in a knapsack of a given capacity.
- Longest Common Subsequence: Finding the longest subsequence present in two sequences.
- Matrix Chain Multiplication: Finding the most efficient way to multiply a given sequence of matrices.
- Coin Change Problem: Finding the number of ways to make change for a given amount with a set of coins.
Example Code: Fibonacci Sequence
#include <stdio.h>
#define MAX 100
int fib[MAX];
void initialize() {
for (int i = 0; i < MAX; i++) {
fib[i] = -1;
}
}
int fibonacci(int n) {
if (fib[n] != -1) {
return fib[n];
}
if (n <= 1) {
return n;
}
fib[n] = fibonacci(n - 1) + fibonacci(n - 2);
return fib[n];
}
int main() {
initialize();
int n = 10; // Change this value for different Fibonacci numbers
printf("Fibonacci number at position %d is %dn", \n, fibonacci(n));
return 0;
}Output
Fibonacci number at position 10 is 55
Example Code: Knapsack Problem
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsack(int W, int wt[], int val[], int n) {
int K[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (wt[i - 1] <= w) {
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
} else {
K[i][w] = K[i - 1][w];
}
}
}
return K[n][W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printf("Maximum value in Knapsack = %d\n", knapsack(W, wt, val, n));
return 0;
}Output
Maximum value in Knapsack = 220