Tabulation और Memoization में अंतर

Memoization बड़े सवाल से नीचे की ओर काम करता है, आगे बढ़ते हुए answers याद रखते हुए, जबकि tabulation पहले छोटे answers की एक table भरता है और बड़े तक बनता है।

In this page:

Memoization
Tabulation
Comparison
When to Use
Practice

Syntax

markup

# Memoization (top-down)
memo = {}
def solve(n):
    if n in memo:
        return memo[n]
    memo[n] = compute(solve(n - 1))
    return memo[n]

# Tabulation (bottom-up)
dp = [0] * (n + 1)
dp[0] = base_value
for i in range(1, n + 1):
    dp[i] = compute(dp[i - 1])

Memoization

Memoization एक problem top-down solve करता है: यह असली सवाल से शुरू होता है जिसका आप answer चाहते हैं और recursively इसे छोटे pieces में तोड़ता है, हर result को पहली बार compute होने पर cache करते हुए ताकि same arguments वाली बाद की calls तुरंत return हों।

उदाहरण: Memoization

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int,int> cache;
int fib(int n) {
	if (n <= 1) return n;
	if (cache.count(n)) return cache[n];
	return cache[n] = fib(n-1) + fib(n-2);
}
int main() { cout << "Top-down from fib(10): " << fib(10); return 0; }

import java.util.*;
public class Main {
	static Map<Integer,Integer> cache = new HashMap<>();
	static int fib(int n) {
		if (n <= 1) return n;
		if (cache.containsKey(n)) return cache.get(n);
		int r = fib(n-1) + fib(n-2);
		cache.put(n, r);
		return r;
	}
	public static void main(String[] args) { System.out.println("Top-down from fib(10): " + fib(10)); }
}

cache = {}
def fib(n):
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]
print("Top-down from fib(10):", fib(10))

#include <stdio.h>
int cache[11]={0}, computed[11]={0};
int fib(int n) {
	if (n <= 1) return n;
	if (computed[n]) return cache[n];
	computed[n] = 1;
	return cache[n] = fib(n-1) + fib(n-2);
}
int main() { printf("Top-down from fib(10): %d", fib(10)); return 0; }

Tabulation

Tabulation उसी तरह की problem bottom-up solve करता है: यह सबसे छोटे base cases से शुरू होता है, एक table order में भरता है, और बिना कभी एक recursive call किए final answer तक बनता है।

उदाहरण: Tabulation

#include <iostream>
using namespace std;
int main() {
	int dp[11]; dp[0]=0; dp[1]=1;
	for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
	cout << "Bottom-up table filled in order, dp[10] = " << dp[10];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] dp = new int[11]; dp[0]=0; dp[1]=1;
		for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
		System.out.println("Bottom-up table filled in order, dp[10] = " + dp[10]);
	}
}

dp = [0]*11
dp[1] = 1
for i in range(2, 11):
    dp[i] = dp[i-1] + dp[i-2]
print("Bottom-up table filled in order, dp[10] =", dp[10])

#include <stdio.h>
int main() {
	int dp[11]; dp[0]=0; dp[1]=1;
	for (int i = 2; i <= 10; i++) dp[i] = dp[i-1] + dp[i-2];
	printf("Bottom-up table filled in order, dp[10] = %d", dp[10]);
	return 0;
}

Comparison

दोनों naive recursion के wasted, repeated computation से बचते हैं, लेकिन वे dependency graph को opposite directions में चलते हैं — memoization सिर्फ वे states compute करता है जो recursion को असल में चाहिए, जबकि tabulation अपनी table में हर state compute करता है चाहे final answer को strictly इसकी ज़रूरत हो या नहीं।

उदाहरण: Comparison

#include <iostream>
using namespace std;
int main() {
	cout << "Memoization computes only states the recursion actually needs; tabulation fills every state";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Memoization computes only states the recursion actually needs; tabulation fills every state");
	}
}

print("Memoization computes only states the recursion actually needs; tabulation fills every state")

#include <stdio.h>
int main() {
	printf("Memoization computes only states the recursion actually needs; tabulation fills every state");
	return 0;
}

When to Use

Memoization ज़्यादा natural महसूस होता है जब आपके पास पहले से एक काम करता recursive solution है और आप बस इसे speed up करना चाहते हैं; tabulation आमतौर पर reason करने में simpler, space-optimize करना आसान है, और बड़े inputs पर recursion-depth stack overflows का जोखिम avoid करता है।

उदाहरण: When to Use

#include <iostream>
using namespace std;
int main() {
	cout << "Have working recursion already? Memoize it. Want iterative, space-optimized code? Tabulate.";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Have working recursion already? Memoize it. Want iterative, space-optimized code? Tabulate.");
	}
}

print("Have working recursion already? Memoize it. Want iterative, space-optimized code? Tabulate.")

#include <stdio.h>
int main() {
	printf("Have working recursion already? Memoize it. Want iterative, space-optimized code? Tabulate.");
	return 0;
}

Practice

कोई universally 'बेहतर' choice नहीं है — memoization चुनें जब recursive structure पहले लिखने में clearer हो, और tabulation चुनें जब आपको iterative code चाहिए या memory usage को precisely control करना हो।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "No universal winner -- pick based on which structure (recursive vs iterative) fits the problem";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("No universal winner -- pick based on which structure (recursive vs iterative) fits the problem");
	}
}

print("No universal winner -- pick based on which structure (recursive vs iterative) fits the problem")

#include <stdio.h>
int main() {
	printf("No universal winner -- pick based on which structure (recursive vs iterative) fits the problem");
	return 0;
}

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson DP Introduction and Memoization Next Lesson → Fibonacci with DP