Memoization
Recursion + Caching: Memoizaiton is a techinique that optimizes recursion by storing the results of subproblems. When the recursive functions is called, it first checks if the result of the current subproblem has been computed before. If so, it retrieves the result from a cache(often an array or hash map) instead of recalculating it.
Top-dwon approach: Memoization typically works in a top-down manner. It starts with the larger problem and recursively breaks it down into smaller subproblems. When a subproblem's reuslt is needed again, it's retrieved from the cache rather than recomputed.
Implementation: It is usually implemented by adding a cache (like an array or dircitonary) to a recursive function.
算法记忆化
备忘录
目的: 减少重复计算
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
Given n, calculate F(n).
Example 1:
Example 2:
Example 3:
Constraints:
0 <= n <= 30
Solution:
class Solution {
public int fib(int n) {
if (n <= 1){
return n;
}
return fib(n - 1) + fib(n - 2);
}
}
// TC: O(2^n)
// SC: O(n)
class Solution {
public int fib(int n) {
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return fibMemo(n, memo);
}
private int fibMemo(int n, int[] memo){
if (n <= 1){
return n;
}
if (memo[n] != -1){
return memo[n];
}
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
}
Dynamic Programming (DP)
Iteration + Table filling: DP solves problems by building up a table fo results. It starts with the smallest subproblems and iteratively solves larger problems using these precomputed solutions:
Bottom-up approach: DP is usually implemented using a bottom-up approach. It solves the smallest subproblems first and uses these to gradually build solutions for larger problems. The final solution is obtained from the last entry in the table.
Implementation: It is typically implemented with loops and an array or matrix to store intermediate results.
class Solution {
public int fib(int n) {
if (n <= 1){
return 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];
}
}
In this example, fib iteratively calculates the Fibonacci sequence by filling up the dp array, starting from the smallest subproblems.
Key Difference:
- Approach: Memoization uses recursion and works top-down, whereas DP uses iteration and works bottom-up.
- Efficiency: Both techniques have the same time complexity, but DP avoids the overhead of recursive function calls, making it slightly more efficient.
- Readability: Memoization may be more intuitive for problems that are naturaly recursive, while DP can be cleaner and easier to understand in other cases due to its iterative nature.
In summary, memoization is useful when you already have a recursive solution, while dynamic programming is typically used when designing an iterative solution from the start.