DP परिचय और Memoization

Dynamic programming छोटी problems के answers sticky notes पर लिखने जैसा है ताकि आप कभी एक जैसी को दो बार solve न करें।

In this page:

DP Idea
Memoization
Overlapping Subproblems
Optimal Substructure
DP Practice

Syntax

markup

memo = {}
def solve(n):
    if n in memo:
        return memo[n]
    if n <= base:
        return base_value
    memo[n] = combine(solve(n - 1), solve(n - 2))
    return memo[n]

DP Idea

Dynamic programming किसी problem को इसे छोटे subproblems में तोड़कर solve करता है, लेकिन इसकी असली power यह notice करने से आती है कि वही subproblem अक्सर बार-बार solve होता है — DP बस हर unique subproblem को एक बार solve करता है और इसे हर दूसरी बार चाहिए होने पर stored answer reuse करता है।

उदाहरण: DP Idea

#include <iostream>
using namespace std;
int main() {
	cout << "DP: break into subproblems, solve each unique one once, reuse the stored answer";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("DP: break into subproblems, solve each unique one once, reuse the stored answer");
	}
}

print("DP: break into subproblems, solve each unique one once, reuse the stored answer")

#include <stdio.h>
int main() {
	printf("DP: break into subproblems, solve each unique one once, reuse the stored answer");
	return 0;
}

Memoization

Memoization DP का top-down flavor है: आप natural recursive solution लिखते हैं, लेकिन कोई काम करने से पहले आप एक cache जांचते हैं यह देखने के लिए कि यह exact call पहले ही answer हो चुकी है या नहीं, और सिर्फ तब compute करते हैं जब नहीं हुई।

उदाहरण: 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 << "fib(10) = " << fib(10) << " (cache checked before recomputing)";
	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 result = fib(n-1) + fib(n-2);
		cache.put(n, result);
		return result;
	}
	public static void main(String[] args) {
		System.out.println("fib(10) = " + fib(10) + " (cache checked before recomputing)");
	}
}

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(f"fib(10) = {fib(10)} (cache checked before recomputing)")

#include <stdio.h>
int cache[11] = {0}; int 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("fib(10) = %d (cache checked before recomputing)", fib(10));
	return 0;
}

Overlapping Subproblems

एक problem में overlapping subproblems होते हैं जब एक naive recursive solution खुद को identical arguments के साथ कई बार call करता है — plain recursive Fibonacci, उदाहरण के लिए, n बढ़ने के साथ fib(2) को exponentially कई बार recompute करता है।

उदाहरण: Overlapping Subproblems

#include <iostream>
using namespace std;
int calls = 0;
int fib(int n) {
	calls++;
	if (n <= 1) return n;
	return fib(n-1) + fib(n-2);
}
int main() {
	fib(10);
	cout << "Naive fib(10) makes " << calls << " calls -- fib(2) alone gets recomputed dozens of times";
	return 0;
}

public class Main {
	static int calls = 0;
	static int fib(int n) {
		calls++;
		if (n <= 1) return n;
		return fib(n-1) + fib(n-2);
	}
	public static void main(String[] args) {
		fib(10);
		System.out.println("Naive fib(10) makes " + calls + " calls -- fib(2) alone gets recomputed dozens of times");
	}
}

calls = 0
def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
fib(10)
print(f"Naive fib(10) makes {calls} calls -- fib(2) alone gets recomputed dozens of times")

#include <stdio.h>
int calls = 0;
int fib(int n) {
	calls++;
	if (n <= 1) return n;
	return fib(n-1) + fib(n-2);
}
int main() {
	fib(10);
	printf("Naive fib(10) makes %d calls -- fib(2) alone gets recomputed dozens of times", calls);
	return 0;
}

Optimal Substructure

एक problem में optimal substructure होता है जब पूरी problem का best answer इसके छोटे pieces के best answers से सीधे assemble किया जा सकता है, पहले से किए choices को फिर से consider किए बिना — यही वह है जो 'store and reuse' को असल में एक correct final answer produce कराता है।

उदाहरण: Optimal Substructure

#include <iostream>
using namespace std;
int main() {
	int best3 = 7, best4 = best3 + 2;
	cout << "Best answer for size 4 (" << best4 << ") built directly from best answer for size 3 (" << best3 << ")";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int best3 = 7, best4 = best3 + 2;
		System.out.println("Best answer for size 4 (" + best4 + ") built directly from best answer for size 3 (" + best3 + ")");
	}
}

best3 = 7
best4 = best3 + 2
print(f"Best answer for size 4 ({best4}) built directly from best answer for size 3 ({best3})")

#include <stdio.h>
int main() {
	int best3 = 7, best4 = best3 + 2;
	printf("Best answer for size 4 (%d) built directly from best answer for size 3 (%d)", best4, best3);
	return 0;
}

DP Practice

किसी भी नई DP problem शुरू करने का एक अच्छा तरीका है plain words में define करना कि एक छोटी state का मतलब क्या है, यह काम करना कि एक बड़ी state छोटी states से कैसे बन सकती है, और सिर्फ तब इसे code में translate करना।

उदाहरण: DP Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Steps: 1) define state in plain words, 2) build bigger state from smaller, 3) translate to code";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Steps: 1) define state in plain words, 2) build bigger state from smaller, 3) translate to code");
	}
}

print("Steps: 1) define state in plain words, 2) build bigger state from smaller, 3) translate to code")

#include <stdio.h>
int main() {
	printf("Steps: 1) define state in plain words, 2) build bigger state from smaller, 3) translate to code");
	return 0;
}

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson Minimum Spanning Tree Prim Next Lesson → Tabulation vs Memoization