Dynamic programming (English: Dynamic programming, DP for short) is a method used in mathematics, computer science, economics, and bioinformatics to solve complex problems by decomposing the original problem into relatively simple sub-problems. In the field of biological information, such as sequence alignment, the idea of ​​dynamic programming is used. The Viterbi algorithm in the hidden Markov model also uses a dynamic programming algorithm.

For a problem, we analyze that the initial state and the recurrence formula are the keys to the solution. For example, the following classic topics:

1. Climbing the stairs ( https://leetcode.com/problems/climbing-stairs/ )

There is a staircase with a height of 10 steps. Walking from bottom to top, each step can only go up by 1 or 2 steps. Find out how many moves there are.

Think about it carefully. This problem is actually very similar to the Fibonacci sequence, and it can also be solved recursively. If we have climbed to the 10th floor at the end, then the last step is either one step or two. In other words, the way we go to the 10th floor is actually the sum of the ways we go to the 8th and 9th floors. That is, F(n) = F(n-2) + F(n-1).

Recursive solution:

def climb(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return climb(n-1) + climb(n-2)

climb(10)

Recursion will be slow and waste a lot of unnecessary resources. The following methods can be considered:

def climb(n):
    way = [0] * n
    way[0] = 1
    way[1] = 2
    for i in range(2, n):
        way[i] = way[i-1] + way[i-2]
    return way[n-1]

# Or 
def climb=(n):
    if n <= 2:
        return n
    else:
        a, b = 1, 2
        for i in range(n-2):
            a, b = b, a + b
        return b

climb(10)

2. Use the least cost to climb stairs ( https://leetcode.com/problems/min-cost-climbing-stairs/ )

Each index of the array is used as a ladder, and the i-th ladder corresponds to a non-negative physical effort cost[i] (the index starts from 0). Every time you climb a ladder, you have to spend the corresponding physical cost value, and then you can choose to continue climbing one ladder or climbing two ladders. You need to find the lowest cost to reach the top of the floor. At the beginning, you can choose the element with index 0 or 1 as the initial ladder. (The length of cost will be [2, 1000].) For example:

It has the same effect as the previous question. In fact, the value of position i is essentially equal to the sum of the minimum value of the previous one and the first two and the value of this position, that is, f[i] = cost[i] + min( f[i-1], f[i-2]).

 def cal_cost(cost):
        dp = [0] * (len(cost) + 1)
        dp[0] = cost[0]
        dp[1] = cost[1]
        
        cost.append(0)
        for i in range(2, len(cost)):
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
            
        return dp[-1]

3. House-robber ( https://leetcode.com/problems/house-robber/ )

You are a professional thief, planning to steal houses along the street. There is a certain amount of cash hidden in each room. The only restrictive factor that affects your theft is that adjacent houses are equipped with interconnected anti-theft systems. If two adjacent houses are broken into by a thief at the same night, the system will automatically alarm . Given an array of non-negative integers representing the amount of money stored in each house, calculate the highest amount you can steal without triggering the alarm device.

When we steal to the i-th house, all we can steal is up to the maximum of the sum of the money stolen by the i-1st house and the i-2th house and the i-th house, that is, dp[ i] = max(nums[i] + dp[i -2], dp[i-1]).

def rob(nums):
    size = len(nums)
    
    if size == 1:
        return nums[0]
    elif size == 2:
        return max(nums[0], nums[1])
    elif size == 0:
        return 0     
    else:
        dp = [0] * size
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        for i in range(2, size):
            dp[i] = max(nums[i] + dp[i-2], dp[i-1])

        return dp[-1]

In fact, we can find that we actually only use the values ​​of dp[i-2] and dp[i-1], then optimize the above method:

def rob(nums):
    now = last = 0
    for i in range(len(nums)):
        now, last = max(last + nums[i], now), now 
    return now