Skip to main content

1D Dynamic Programming

The 1D dynamic programming is a dynamic programming algorithm that uses a single array to store the intermediate results, where the final solution may depend on the previous states.

A classical example is the fibonacci sequence, even though it can be solved using algebraic equations, it is a good example to show the power of dynamic programming.

This kinds of linear recurrent relations is also widely studied in the field of combinatorics. Some linear recurrent relations can be solved using algebraic equations, but some cannot, this will be the case where dynamic programming is the "only" way to solve it. (perhaps)

Codes​

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

Applications​

Leetcode 3494​

Intuition

This problem is particularly tricky because you are required to use backtracking to find the minimum amount of time to brew the potions for each round.

Combined with the reversed dp order, it takes me a few hours to figure out the solution.

Solution
class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n,m=len(skill),len(mana)
        init=[0]*(n+1)
        for i in range(m):
            for j in range(n):
                init[j+1]=max(init[j+1],init[j])+skill[j]*mana[i]
            for j in range(n-1,0,-1):
                init[j]=init[j+1]-skill[j]*mana[i]
        return init[-1]