Dynamic programming

Problem:
Write a function fib that takes in a number argument, n, and returns the n-th number of the Fibonacci sequence.
The 0-th number of the sequence is 0.
The 1-st number of the sequence is 1.
To generate further numbers of the sequence, calculate the sum of previous two numbers.
Solve this recursively.

# test 00
fib(0); # -> 0

Approach:

What is fibonacci series?

When we try to solve this problem using recursion, it looks like below. The return values 0 & 1 seen in this picture are return values from base cases.

Like we discussed in the base case; it’s time to think how to build the final solution with the help of answers from base case.
That is; by adding the results of base cases.
Once you are aware of how to solve the problem, apply memoization. What is memoization? Observe the below tree & fib(4) is calculated twice for example. Not only feb(4), but many other sub problems are also calculated twice. Can you avoid it? How about storing the reuslt of sub problem when you calculate it for the first time & then each time you try to solve a sub problem, first check whether it’s already solved in / not,
if solved : pick the stored result.
if not solved : solve it & store the result.
That’s memoization..

Let’s see memoization in action for 1 scenario. We started calculating the result from base cases as shown below & on the process, we calculated result for node 2.
Will check the memo for result of node 2 –> since it’s first time, will not find it –> hence, insert into memo.
The work continues & will again get a need to calculate the result of node 2 during which, the result can be find in the memo & hence instead if calculating once again, will pick the result from memo.

It’s time to code the same thing what we diccussed above..
First, let’s solve the problem with out memoization.

def fib(n):
  if n == 0 or n == 1:
    return n
  return fib(n - 1) + fib(n - 2)

Now, integrate the memoization into this problem.

def fib(n):
    memo = {}
    return _fib(n, memo)

def _fib(n, memo):
    if n == 0 or n == 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = _fib(n - 1, memo) + _fib(n - 2, memo)
    return memo[n]

Problem
Write a function sum_possible that takes in an amount and a list of positive numbers. The function should return a boolean indicating whether or not it is possible to create the amount by summing numbers of the list. You may reuse numbers of the list as many times as necessary.
You may assume that the target amount is non-negative.

# test 00
sum_possible(8, [5, 12, 4]) # -> True, 4 + 4

Approach
Let’s see how can be solve the below example of amount 4 can be formed with the numbers 1, 2 & 3.
Here bigger problem is 4
Our goal is to make this problem smaller & smaller –> From 4, we can subtract 1, 2 & 3, which results in smaller problems –> Then, go on subtracting the numbers from that sub problmes until 0 is reached. Hitting 0 means that the number is formed.
And while solving the problem, we also need to take care that the numbers are subtracted from sub problems, result should not be -ve.

And, how do you know the result?
That’s nothing but the numbers along the branch of tree.

Solution

def sum_possible(amount, numbers):
    return _sum_possible(amount, numbers, {})

def _sum_possible(amount, numbers, memo):
    if amount in memo:
        return memo[amount]
    if amount < 0:
        return False
    if amount == 0:
        return True
    for num in numbers:
        if _sum_possible(amount - num, numbers, memo):
            memo[amount] = True
            return True
    memo[amount] = False
    return False