Top DP समस्याएँ

#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 << "Stored once, reused instantly on later requests: fib(15) = " << fib(15); 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("Stored once, reused instantly on later requests: fib(15) = " + fib(15)); }
}

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("Stored once, reused instantly on later requests: fib(15) =", fib(15))

#include <stdio.h>
int cache[16]={0}, computed[16]={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("Stored once, reused instantly on later requests: fib(15) = %d", fib(15)); return 0; }

Login to try C/C++/Java code in the editor

#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 << "fib(10) = " << dp[10] << " built bottom-up, no recomputation";
	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("fib(10) = " + dp[10] + " built bottom-up, no recomputation");
	}
}

dp = [0]*11
dp[1] = 1
for i in range(2, 11):
    dp[i] = dp[i-1] + dp[i-2]
print("fib(10) =", dp[10], "built bottom-up, no recomputation")

#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("fib(10) = %d built bottom-up, no recomputation", dp[10]);
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
	int n = 5;
	int dp[6]; dp[0]=1; dp[1]=1;
	for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
	cout << "Ways to climb " << n << " stairs (1 or 2 at a time): " << dp[n];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 5;
		int[] dp = new int[6]; dp[0]=1; dp[1]=1;
		for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
		System.out.println("Ways to climb " + n + " stairs (1 or 2 at a time): " + dp[n]);
	}
}

n = 5
dp = [0]*(n+1)
dp[0] = dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(f"Ways to climb {n} stairs (1 or 2 at a time): {dp[n]}")

#include <stdio.h>
int main() {
	int n = 5;
	int dp[6]; dp[0]=1; dp[1]=1;
	for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
	printf("Ways to climb %d stairs (1 or 2 at a time): %d", n, dp[n]);
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
	int dp[6] = {0};
	for (int i = 0; i < 3; i++)
		for (int w = capacity; w >= weights[i]; w--)
			dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
	cout << "Best value under capacity " << capacity << ": " << dp[capacity];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] weights = {2,3,4}, values = {3,4,5};
		int capacity = 5;
		int[] dp = new int[6];
		for (int i = 0; i < 3; i++)
			for (int w = capacity; w >= weights[i]; w--)
				dp[w] = Math.max(dp[w], dp[w-weights[i]] + values[i]);
		System.out.println("Best value under capacity " + capacity + ": " + dp[capacity]);
	}
}

weights, values, capacity = [2,3,4], [3,4,5], 5
dp = [0]*(capacity+1)
for i in range(3):
    for w in range(capacity, weights[i]-1, -1):
        dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
print("Best value under capacity", capacity, ":", dp[capacity])

#include <stdio.h>
int main() {
	int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
	int dp[6] = {0};
	for (int i = 0; i < 3; i++)
		for (int w = capacity; w >= weights[i]; w--)
			if (dp[w-weights[i]] + values[i] > dp[w]) dp[w] = dp[w-weights[i]] + values[i];
	printf("Best value under capacity %d: %d", capacity, dp[capacity]);
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
	cout << "4 questions: what is a state, how is it built from smaller states, base cases, iteration order";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("4 questions: what is a state, how is it built from smaller states, base cases, iteration order");
	}
}

print("4 questions: what is a state, how is it built from smaller states, base cases, iteration order")

#include <stdio.h>
int main() {
	printf("4 questions: what is a state, how is it built from smaller states, base cases, iteration order");
	return 0;
}

Login to try C/C++/Java code in the editor