Leetcode 75 Study Plan - Dynamic Programming

[41071119H-Irene]

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).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

[41071119H-Irene]

509. Answer

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        a, b = 0, 1
        for i in range(2, n+1):
            # for 迴圈做斐波那契數列的計算
            a, b = b, a+b
        return b

[41071119H-Irene]

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?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
4. 2 steps + 1 step

[41071119H-Irene]

70. Answer

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 2:
            # 防呆機制
            return 1;
         # dp數組紀錄爬每階的方法數   
        dp = [0 for _ in range(n)];
        dp[0] = 1;
        dp[1] = 2;

        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2];

        return dp[-1];

[41071119H-Irene]

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.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

[41071119H-Irene]

746. Answer

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 有幾階階梯
        dp = [0] * (n + 1)
        #以「迭代」的方式去計算
        dp[0], dp[1] = cost[0], cost[1]
        for i in range(2, n+1):
            dp[i] = min(dp[i-1], dp[i-2]) + (cost[i] if i < n else 0)
            # 我們可以從前一階或前兩階中選擇一個花費最少的步驟到達當前階梯
        return dp[n]

[41071119H-Irene]

62. Answer

class Solution:
    cache = {}
    # 記錄已經計算過的結果
    def uniquePaths(self, m: int, n: int) -> int:
        #定義網格的行、列
        if (m, n) in self.cache: 
            return self.cache[(m,n)]
        if m == 1 or n == 1:
            # 只有1種路徑
            result = 1
        else:
            result = self.uniquePaths(m-1, n) + self.uniquePaths(m, n- 1)
            # 計算長方形的路徑數
        self.cache[(m, n)] = result
        return result

[41071119H-Irene]

62. Unique Path

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
4. ```

[41071119H-Irene]

小知識✨

動態規劃 (Dynamic Programming): 大問題拆解成小問題

只要寫出遞迴式，就可以小範圍開始解決問題。