Ch7- Dynamic programming

1. Dynamic programming

Q1. Make ‘1’

Q2. Ant soldier

Q3. Floor construction

Q4. Compose currency

1. Dynamic programming

Dynamic programming is the algorithm which don’t calculate again already solved problem. Fibonacci numbers is prime example. It is sum of the two preceding ones.

This can be expressed in the following recurrence relation.

This sequence can be expressed as array or list in programming. Python use list type and C/C++ and java use array type to implement sequence. Let’s solve the fibonacci numbers example by using formula. If the N th Fibonacci number is f(n), it repeatedly call the function f to finding f(4) which is fourth fibonacci numbers.

The code is like this

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo( x - 1 ) + fibo( x - 2 )
print(fibo(4))

But if you implement fibonacci numbers like this code. It can be problem because processing time sharply increase when N is increase. Let’s look at this figure.

You might realize that same function is called repeatedly when look at the f(3). f(3) called three times. It means you can use recursive function but it is inefficient. You can use dynamic programming in this problem. but there are conditions to using it.

1. It need to be able to divide the big problem into the small problem.
2. The answer to the small question is the answer to the big question

Memoization is one of method to implement dynamic programming. It save the result of formula to memory store and when calling the same formula, bring the result from memory store. The implement is very simple. It just save the result to list and get the results from list when it need in the middle of recursive function. The code is like this

# Initialize list
d = [0] * 100

# Implement recursive function
def fibo(x):
    # Determinate condition
    if x == 1 or x == 2:
        return 1
    # Return the result if it is the same problem
    if d[x] != 0:
        return d[x]
    # Return the result if it is unsolved problem
    d[x] = fibo(x -1) + fibo(x - 2)
    return d[x]

print(fibo(99))

# 218922995834555169026

To summarize this, Dynamic programming is dividing big problem to small problem and if it is same problem, using the same result to solve problem. The process of quick sort is similar like this. It divide the list to sort but quick sort is classified as “divide and conquer” algorithm. The different point with dynamic programming is that the divided list of dynamic programming affects each other.

Take quick sort as an example, after setting pivot, the position of pivot is not recalculated until to change new pivot. But dynamic programming recalculate the problem. So following figure is the example of using memorization to f(6) fibonacci numbers problem and it visits the white nodes.

Let’s check the functions we called

d = [0] * 100

def fibo(x):
    print('f(' + str(x) + ')', end =' ')
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

fibo(6)

# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

This method use recursive function to implement dynamic programming. It called as “Top-down” method using small problem to solve big problem

In contrast, If it use for loop, it called as “Bottom-up” method. Following code is solution by using bottom-up method to fibonacci numbers

# Create DP table
d = [0] * 100

# First and second fibonacci numbers is '1'
d[1] = 1
d[2] = 2
n = 99

# Bottom-up dynamic programming 
for i in range(3, n+1):
    d[i] = d[i -1] + d[i -2]

print(d[n])
# 218922995834555169026

“DP table” is the list to store result of bottom-up method in dynamic programming. If you remember the process to solve fibonacci numbers, it is more easy to solve other dynamic programming problems. Of course, there is difficult problem to use 3-dimension list. We study this kind problem in “Floyd-washall” of “Shortest path” algorithms. But most of dynamic problems in coding test is not too difficult so next questions are enough to solve coding test problems.

Q1 Make ‘1’

When given integer X, the operator to use X is following four steps.

1. If X is divided by 5, divide 5.
2. If X is divided by 3, divide 3.
3. If X is divided by 2, divide 2.
4. Minus 1 to X

Peter want to make ‘1’ by using these operator when given X. Print minimum number of operation.

For example, If X is 26, 3 times is minimum number of operation

1. 26 -1 = 25
2. 25/5 = 5
3. 5/5 = 1

Solution

This problem is prime dynamic programming problem. This problem can be presented by following formula.

Let’s make the code of bottom-up dynamic programming by using this formula. The reason why plus 1 to end of formula is for finding number of operation. It is easy to use min() method in python when you want to find more lesser number between two numbers.

# Input X
x = int(input())

# Initialize table
d = [0] * 30001

for i in range(2, x+1 ):
    d[i] = d[i-1] + 1
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
    if i % 5 == 0:
        d[i] = min(d[i], d[i//5] + 1)

print(d[x])
# 26
# 3

Q2. Ant soldier

Ant soldier will attack to village of locusts to plunder food. There are few of food storage in village and it is in a row. Locust scout can recognize when storage in a row is under attack. So ant soldier attack the storage more than a step away from others to evade surveillance. For example, there are four storage in a row.

{ 1, 3, 1, 5 }

Get ConfidenceCoding’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The ant soldier can get 8 foods when attacking second storehouse and fourth storehouse. Soldier want to get maximum foods. Make the program can get maximum foods when given N numbers of storehouse.

Solution

N is 4 and there are foods in storage. The number of cases is 8 and the answer is 8 in the 7th case of following figure

The solution is calculating the cases of attack in the order.

1. If soldier attack ( i-1 )th storage, it is impossible to attack current storage.

2. If soldier attack ( i-2 )th storage, it is possible to attack current storage.

So the solution is choosing the case which get more foods. It doesn’t need to consider attacking after ( i-3 )th storages because soldier can attack storage where is more than one space. So the formula is like this.

This code is bottom-up method

n = int(input())

array = list(map(int, input().split() ))

# Initialize DP table
d = [0] * 100

d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2,n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

print(d[n -1])

Q3 Floor construction

There are tiles which is shape of rectangle and length is 2, width is N. Peter cover the floor with these tiles which are 1 x 2 tile, 2 x 1 tile, 2 x 2 tile.

Make the program to cover the floor and print the remainder divided by 796,796. For example, the number of cases is 5 when covering the 2 x 3 floor.

Solution

This question is basic level of dynamic programming problem. The reason why divide 796,796 is the result can be too much large value so it get the remainder when calculating specific number. For example, the number of cases is like these when N is 3.

There are two case to forming formula.

1. There is one case to use 2 x 1 tile if it is already filled with tiles that the width is i-1.

2. There are two cases to use two 1 x 2 tiles or two 2x 2 tiles if is already filled with tiles that the width is i-2.

The maximum size of tile is 2 x 2 so it doesn’t need to consider the width is over i-3. The formula is like this.

There are two cases if is already filled with tiles that the width is i-2. These two are different so it can be presented like following formula.

The code is like this

n = input(input())

# initialize DP table
d = [0] * 1001

d[1] = 1
d[2] = 3
for i in range(3, n+1):
    d[i] = (d[i-1] + 2 * d[i-2]) % 796796

print(d[n])

Q4. Compose currency

There are ‘N’ type of currency. Peter want to make sum as ‘M’ by using minimum number of currency. If the order of currency is different, it is recognized different composition. For example, there are 2, 3 currency and want to compose 15. The answer is using 3 for 5 times. if it is impossible to compose, return -1

Solution

This question is similar with greedy problem but it can’t use greedy algorithm because the largest currency is not a multiple of small currency. The minimum number of currency is a for making sum ‘i’ and unit of currency is ‘k’. The formula is like this.

a(i-k) is minimum number of currency for make (i-k), i = index, k = currency

To solve this problem, assign K to list and then implement memoization considering index of currency. For example N = 3, K = 7 and unit of currency is 2, 3, 5.

step1. Initialize index to ‘0’ and max value. ‘0’ is the case when it isn’t used.

step2. Firstly check the currency ‘2’. ‘1’ is in the index 2. It means make sum ‘2’ by using 1 piece of ‘2’. And ‘2’ is in index 4. It means make sum ‘4’ ( 2 + 2 ) by using 2 pieces of ‘2’. If the value in index is 10,001, it means an amount that cannot be composed with ‘2’.

step3. Check the currency ‘3’. ‘2’ is in index 5. It means make sum ‘5’ ( 2 + 3 ) by using one piece of ‘2’ and one piece of ‘3’.

step4. Check the currency ‘5’. ‘2’ is in index 7. Index 7 was ‘3’ in previous step but it update to small value ‘2’. ‘3’ is sum of ( 2 + 2 + 3 ) and ‘2’ is sum of (2 + 5).

In conclusion, the minimum number of currency to make sum ‘7’ is 2. Let’s look at the code.

n,m = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input() ))
    
# Initialize DP table
d = [10001] * (m+1)

d[0] = 0
for i in range(n):
    for j in range(array[i], m+1):
        # if there is method for making sum of currency
        if d[ j-array[i] ] != 10001:
            d[j] = min(d[j], d[ j-array[i] ] + 1)

print(d[m])

"""
3 7
2
3
5

2
"""

Summary


1. Dynamic programming is the method to make big problem to small problem

2. Top-down Dynamic programming use recursive function.

3. Bottom-up Dynamic programming use for loop.