LeetCode Day 38 Dynamic Programming (1/17)

Move to the practices of Dynamic Programming, its a huge block, including sections on basic topics, knapsack problems, house robber, stock problems and subsequence problems.

1. Fundamentals of Dynamic Programming

1.1 What is Dynamic programming

Dynamic programming in both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

1.2 Steps to Solve Dynamic Programming Problems

1. Determine the meaning of the dp table and subscripts.
2. Determining the recursive formula
3. How the dp array is initialised
4. Determine the order of traversal
5. Derive dp arrays by example

When I see this, it feels like dp is a bit like Markov property in the sense that when a stochastic process has a conditional probability distribution of future states that depends only on the current state, given the present state and all past states. It’s a bit of a stretch to say that, but it’s all an iterative process where one step before affects the next.

1.3 How dynamic programming should be debugged

To do the topic of dynamic programming, before writing the code, be sure to simulate the state transfer on the dp array for the specific case, and have a good idea of what you want to do, and make sure that what you push out at the end is the desired result.

Then write the code, if the code does not pass, print the dp array to see if it is not the same as their own pre-simulation where different.

If the printout and their own pre-simulation of the derivation is the same, then their own recursion formula, initialisation or traversal order is a problem. If it’s not the same as your pre-simulation, then there’s a problem with the implementation details of the code.

Questions

Question 1

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

This is an easy question because the recursive formula has been given to us: F(n) = F(n - 1) + F(n - 2), and the initialisation has been given: F(0) = 0, F(1) = 1

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

Question 2

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

The third step can be deduced recursively from the different walks of the first two steps, and the same goes for the steps after that, so this is also a problem solved by dynamic programming. And reasoning out the results of the first 5 steps will show that this is still the Fibonacci numbers from the previous question.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return n
        
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

Question 3

746. Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

dp[i - 1] Jumping to dp[i] costs dp[i - 1] + cost[i - 1].

dp[i - 2] Jumping to dp[i] costs dp[i - 2] + cost[i - 2].

In order to minimise the cost, choose dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost) + 1)
        dp[0] = 0 
        dp[1] = 0 
        for i in range(2, len(cost) + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[len(cost)]