Dynamic Programming

	import time

	# Time: O(2^n)
	# Space: O(2^n)
	def Fib1(n):
	if (n == 1 or n == 2):
	return 1
	return Fib1(n-1) + Fib1(n-2)

	# Time: O(n)
	# Space: O(n)
	def Fib2(n):
	A = [0] * max(n, 2)
	A[0] = 1
	A[1] = 1
	for i in range(2, n):
	A[i] = A[i-1] + A[i-2]
	return A[n-1]

	# Time: O(n)
	# Space: O(1)
	def Fib3(n):
	cur = 1
	prev = 1
	for i in range(2, n):
	tmp = cur
	cur = cur + prev
	prev = tmp
	return cur

	# Get how long each function takes in seconds
	if __name__ == "__main__":
	start_time = time.time()
	Fib1(50)
	print("Fib 1 : %s seconds" % (time.time() - start_time))
	start_time = time.time()
	Fib2(50)
	print("Fib 2 : %s seconds" % (time.time() - start_time))
	start_time = time.time()
	Fib3(50)
	print("Fib 3 : %s seconds" % (time.time() - start_time))

view raw fibonacci.py hosted with ❤ by GitHub

	# Time: O(n*\|D\|)
	# Space: O(n)
	def change_making(D, n):
	# Set both rows to all 0's
	row_prev = [0] * (n+1)
	row_cur = [0] * (n+1)

	# Fill in table
	for i in range(len(D)): # for i in {0, 1, ..., \|D\|-1}
	for j in range(n+1): # for j in {0, 1, ..., n}
	# Using D[d]. Set to inf if we can't use D[d] (it's too large).
	using_last_coin = row_cur[j-D[i]] + 1 if j - D[i] >= 0 else float('inf')

	# Not using D[d]. Set to inf if no other coins to use.
	not_using_last_coin = row_prev[j] if i >= 1 else float('inf')

	# Select minnimum of using last coin and not using last coin if we aren't at the Base Case
	row_cur[j] = 0 if j == 0 else min(using_last_coin, not_using_last_coin)

	# Only go to next row if we aren't on the last one
	if (i < len(D)-1):
	row_prev = row_cur
	row_cur = [0] * (n+1)

	return row_cur[n]


	if __name__ == "__main__":
	print(change_making([1, 3, 7, 10], 14))

view raw change_making.py hosted with ❤ by GitHub

Video