WDSAP24-DP-I Code Snippets

climbing_stairs.py

# assuming we can take 1, 2, or 3 steps 

n = int(input()) # the number of steps 
k = int(input()) # the unmber of steps we can take
dp = [-1 for i in range(n + 1)]

# def number_of_ways(n):
# 	if n == 0: 
# 		return 1
# 	if n == 1: 
# 		return 1
# 	if n == 2: 
# 		return 2
# 	if dp[n] != -1: # we have computed this before
# 		return dp[n]
# 	dp[n] = number_of_ways(n - 1) + \
# 		    number_of_ways(n - 2) + \
# 		    number_of_ways(n - 3)
# 	return dp[n]

# k^n: when written recursively

def number_of_ways(n):
	if n == 0: 
		return 1
	if dp[n] == -1:
		return dp[n]
	sum_ways = 0
	for i in range(1, k + 1):
		if n - i >= 0: 
			sum_ways += number_of_ways(n - i)
	dp[n] = sum_ways
	return dp[n]

print(number_of_ways(n))

memo.py

# O(n)

n = int(input())
cache = [False for i in range(n + 1)]
cache_val = [0 for i in range(n + 1)]

def f(n):
	if n == 0: 
		return 0
	if n == 1: 
		return 1
	if cache[n] == True: 
		return cache_val[n]
	cache_val[n] = f(n - 1) + f(n - 2)
	cache[n] = True
	return cache_val[n]

print(f(n))

memo_2.py

# O(n)

n = int(input())
dp = [-1 for i in range(n + 1)]

def f(n):
	if n == 0: 
		return 0
	if n == 1: 
		return 1
	if dp[n] != -1: 
		return dp[n]
	dp[n] = f(n - 1) + f(n - 2)
	return dp[n]

print(f(n))

memo_fib.cpp

#include <iostream>
#include <vector>

using namespace std;

vector<bool> cache;
vector<int> cache_val;

int f(int n) {
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    if (cache[n])
        return cache_val[n];
    cache_val[n] = f(n - 1) + f(n - 2);
    cache[n] = true;
    return cache_val[n];
}

int main() {
    int n;
    cin >> n;
    cache.resize(n + 1);
    cache_val.resize(n + 1);
    cout << f(n) << '\n';
}

recursive_fib.cpp

#include <iostream>

using namespace std;

int f(int n) {
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return f(n - 1) + f(n - 2);
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << '\n';
}