[toc]

OVERVIEW:

Five Steps:

DP Array (DP Table) and Index Meaning:

  • The DP array (dp) is a table where each entry dp[i] represents the solution to a subproblem related to the problem you’re solving.
  • The index i typically corresponds to some parameter or state in the problem, such as length, position, or another relevant metric.

Recurrence Relation (Recursive Formula):

  • This is the formula that defines how to compute dp[i] based on previously computed values in the DP table and possibly other input parameters.

  • For example, if you’re solving a problem related to finding the minimum cost to reach the end of an array, dp[i] might represent the minimum cost to reach index i. The recurrence relation could be something like:

    1
    2

    dp[i] = cost[i] + min(dp[i-1], dp[i-2])

    This formula states that to compute dp[i], you add the cost at index i to the minimum of the costs of reaching the previous two indices.

Initialization of DP Array:

  • Before applying the recurrence relation, you need to initialize the DP array.
  • Initialization depends on the problem. Often, it involves setting up base cases that are directly known without computation.
  • Example: If dp[0] represents the base case, it might be initialized as dp[0] = 0.

Traversal Order:

  • The order in which you populate the DP table matters and is usually sequential.
  • Depending on the problem, traversal might be from left to right, right to left, or more complex patterns (like matrix DP).
  • Ensure each entry dp[i] depends only on the entries already computed before it.

Example of DP Array Deduction:

  • Let’s take an example problem where you’re finding the maximum sum subarray. Given an array nums, dp[i] could represent the maximum sum of a subarray ending at index i.
  • Initialization: dp[0] = nums[0] (base case)
  • Recurrence relation: dp[i] = max(nums[i], dp[i-1] + nums[i])
  • Traversal: From i = 1 to n-1, where n is the length of the array.

Example deduction for array [1, -2, 3, -1, 2]:

  • Initialize: dp[0] = 1

  • Compute sequentially:

    1
    2
    3
    4
    scssCopy codedp[1] = max(-2, 1 - 2) = -1
    dp[2] = max(3, -1 + 3) = 3
    dp[3] = max(-1, 3 - 1) = 2
    dp[4] = max(2, 2 + 2) = 4

Therefore, dp array for the maximum sum subarray problem would be [1, -1, 3, 2, 4].

509. Fibonacci Number

Easy

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,

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

Given n, calculate F(n).

Example 1:

1
2
3
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        if(n < 2) return n-1;
        for(int i = 2; i < n+1; i++){
            dp[i] = dp[i-1] + dp[i-2];
            System.out.println(dp[i]);
        }
        return dp[n];
    }
}

Meaning of DP Array and Indices:

  • The DP array dp is used to store Fibonacci numbers. Specifically, dp[i] represents the Fibonacci number at index i.

Recurrence Relation (Recursive Formula):

  • The problem provides the recurrence relation directly: dp[i] = dp[i - 1] + dp[i - 2].
  • This formula states that each Fibonacci number (starting from the third) is the sum of the two preceding Fibonacci numbers.

Initialization of DP Array:

  • Initialization is provided in the problem statement:

    dp[0] = 0; dp[1] = 1;

  • This initializes the first two Fibonacci numbers, where dp[0] is 0 and dp[1] is 1.

Traversal Order:

  • From the recurrence relation dp[i] = dp[i - 1] + dp[i - 2], it’s evident that dp[i] depends on dp[i - 1] and dp[i - 2].
  • Therefore, to compute each Fibonacci number up to a given index n, you traverse from i = 2 to n.

70. Climbing Stairs

Easy

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:

1
2
3
4
5
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2] ;
        }
        return dp[n];
    }
}

https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html#%E6%80%9D%E8%B7%AF

746. Min Cost Climbing Stairs

Easy

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:

1
2
3
4
5
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//dp[i] 跳到i上面就立马付钱 （my initial method)
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[]dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i < cost.length; i++){
            dp[i] = cost[i] + Math.min(dp[i-2], dp[i-1]);
        }
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);

    }
}
//dp[i]跳到i上，付上一步的钱
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];

        // 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0
        dp[0] = 0;
        dp[1] = 0;

        // 计算到达每一层台阶的最小费用
        for (int i = 2; i <= len; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[len];
    }
}