Problem Statement
What is the key principle behind dynamic programming?
Explanation
Dynamic programming solves problems by breaking them into overlapping subproblems and storing the solutions to avoid redundant computation. This is called memoization in top-down approach or tabulation in bottom-up approach.
The key insight is that many problems have overlapping subproblems, meaning the same subproblem is solved multiple times. By storing results, we avoid recalculating them. For example, in Fibonacci, F of 5 requires F of 4 and F of 3, but F of 4 also requires F of 3, so we compute F of 3 twice without memoization. Dynamic programming stores F of 3 once and reuses it.
Code Solution
SolutionRead Only
// Without DP - Exponential time
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2); // Recalculates same values
}
// Time: O(2^n)
// With DP - Memoization
int fibMemo(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; // Return stored result
memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
return memo[n];
}
// Time: O(n)
// With DP - Tabulation
int fibTab(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];
}
// Time: O(n), Space: O(n)Practice Sets
This question appears in the following practice sets:
