WikiGalaxy
Memoization Technique
Fibonacci Sequence
Concept Explanation:
Memoization is a technique used to optimize recursive algorithms by storing previously computed results. It helps in reducing time complexity by avoiding redundant calculations. A classic example is calculating the Fibonacci sequence.
Example Code:
public class Fibonacci {
private static Map memo = new HashMap<>();
public static int fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println(fib(10)); // Output: 55
}
}
Console Output:
55
Factorial Calculation
Concept Explanation:
Memoization can also be applied to factorial calculations, especially when calculating factorials for a range of numbers repeatedly.
Example Code:
public class Factorial {
private static Map memo = new HashMap<>();
public static long factorial(int n) {
if (n <= 1) return 1;
if (memo.containsKey(n)) return memo.get(n);
long result = n * factorial(n - 1);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println(factorial(5)); // Output: 120
}
}
Console Output:
120
Climbing Stairs Problem
Concept Explanation:
The Climbing Stairs problem is a classic dynamic programming problem that can be solved efficiently using memoization to store the number of ways to reach each step.
Example Code:
public class ClimbingStairs {
private static Map memo = new HashMap<>();
public static int climbStairs(int n) {
if (n <= 2) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = climbStairs(n - 1) + climbStairs(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println(climbStairs(5)); // Output: 8
}
}
Console Output:
8
Longest Common Subsequence
Concept Explanation:
The Longest Common Subsequence (LCS) problem can be optimized using memoization to store intermediate results, avoiding recalculations and improving efficiency.
Example Code:
public class LCS {
private static Map memo = new HashMap<>();
public static int lcs(String s1, String s2, int m, int n) {
if (m == 0 || n == 0) return 0;
String key = m + "," + n;
if (memo.containsKey(key)) return memo.get(key);
if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
int result = 1 + lcs(s1, s2, m - 1, n - 1);
memo.put(key, result);
return result;
} else {
int result = Math.max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
memo.put(key, result);
return result;
}
}
public static void main(String[] args) {
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
System.out.println(lcs(s1, s2, s1.length(), s2.length())); // Output: 4
}
}
Console Output:
4
Minimum Path Sum
Concept Explanation:
In grid-based problems like finding the minimum path sum, memoization can be used to store the minimum sum at each cell, thereby optimizing the path calculation.
Example Code:
public class MinPathSum {
private static Map memo = new HashMap<>();
public static int minPathSum(int[][] grid, int m, int n) {
if (m == 0 && n == 0) return grid[0][0];
String key = m + "," + n;
if (memo.containsKey(key)) return memo.get(key);
int result;
if (m == 0) {
result = grid[m][n] + minPathSum(grid, m, n - 1);
} else if (n == 0) {
result = grid[m][n] + minPathSum(grid, m - 1, n);
} else {
result = grid[m][n] + Math.min(minPathSum(grid, m - 1, n), minPathSum(grid, m, n - 1));
}
memo.put(key, result);
return result;
}
public static void main(String[] args) {
int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
System.out.println(minPathSum(grid, 2, 2)); // Output: 7
}
}
Console Output:
7
