DP के साथ Fibonacci

#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 << "Stored values turn exponential recursion into fib(10) = " << dp[10] << " in linear time";
	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("Stored values turn exponential recursion into fib(10) = " + dp[10] + " in linear time");
	}
}

dp = [0]*11
dp[1] = 1
for i in range(2, 11):
    dp[i] = dp[i-1] + dp[i-2]
print(f"Stored values turn exponential recursion into fib(10) = {dp[10]} in linear time")

#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("Stored values turn exponential recursion into fib(10) = %d in linear time", dp[10]);
	return 0;
}

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

#include <iostream>
using namespace std;
int main() {
	int prev2 = 0, prev1 = 1;
	for (int i = 2; i <= 10; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }
	cout << "Only 2 variables needed, fib(10) = " << prev1;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int prev2 = 0, prev1 = 1;
		for (int i = 2; i <= 10; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }
		System.out.println("Only 2 variables needed, fib(10) = " + prev1);
	}
}

prev2, prev1 = 0, 1
for i in range(2, 11):
    prev2, prev1 = prev1, prev1 + prev2
print("Only 2 variables needed, fib(10) =", prev1)

#include <stdio.h>
int main() {
	int prev2 = 0, prev1 = 1;
	for (int i = 2; i <= 10; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }
	printf("Only 2 variables needed, fib(10) = %d", prev1);
	return 0;
}

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

#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 << "Recursive shape kept, 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("Recursive shape kept, 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("Recursive shape kept, 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("Recursive shape kept, fib(10) = %d", fib(10)); return 0; }

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

#include <iostream>
using namespace std;
int main() {
	cout << "Naive recursion: O(2^n); DP (memo or tabulation): O(n), each subproblem solved once";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Naive recursion: O(2^n); DP (memo or tabulation): O(n), each subproblem solved once");
	}
}

print("Naive recursion: O(2^n); DP (memo or tabulation): O(n), each subproblem solved once")

#include <stdio.h>
int main() {
	printf("Naive recursion: O(2^n); DP (memo or tabulation): O(n), each subproblem solved once");
	return 0;
}

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

#include <iostream>
using namespace std;
int main() {
	cout << "Fibonacci's recursion tree makes overlapping subproblems easy to see -- the classic first DP example";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Fibonacci's recursion tree makes overlapping subproblems easy to see -- the classic first DP example");
	}
}

print("Fibonacci's recursion tree makes overlapping subproblems easy to see -- the classic first DP example")

#include <stdio.h>
int main() {
	printf("Fibonacci's recursion tree makes overlapping subproblems easy to see -- the classic first DP example");
	return 0;
}

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