Dynamic programming chapter 2: Fibonacci number + Stair climbing + Use minimum cost of stair climbing

The article directories

• • • 509. Fibonacci numbers
    • 70. Climbing stairs (exactly the same dynamic equation as Fibonacci number)
    • 746. Climb stairs at minimal cost

509. Fibonacci numbers

Fibonacci numbers, usually denoted by F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each successive digit is the sum of the preceding two. That is:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2), where n > 1 gives you n, please calculate F(n).

Example 1:

Input: 2 Output: 1 Description: F(2) = F(1) + F(0) = 1 + 0 = 1 Example 2:

Input: 3 Output: 2 Description: F(3) = F(2) + F(1) = 1 + 1 = 2 Example 3:

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

Dynamic penta:

1. The Fibonacci value of the ith number is dp[I].
2. Determine the recursion formula they have given us the recursion formula directly: the state transition equation dp[I] = dp[i-1] + dp[i-2];
3. Dp [0] = 0; dp[0] = 0; dp[1] = 1;
4. Determine the traversal order from the recursive formula dp[I] = dp[i-1] + dp[i-2]; As can be seen, dp[I] is dependent on dp[i-1] and dp[i-2], so the traversal sequence must be traversal from front to back
5. Dp [I] = dp[i-1] + dp[i-2],

class Solution {
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        returndp[n]; }}Copy the code

Simplification, first, simplification of n<=1; Second, because we’re only returning one element of the array, not the entire DP array, we can simplify by getting rid of the DP array.

class Solution {
    public int fib(int n) {
        if(n<=1) return n;
        int dp1=0;
        int dp2=1;
        for(int i = 2; i <= n; i++) { int temp = dp2; dp2= dp1+dp2; Dp1 = temp; // the value of dp1 is changed}returndp2; // The last element}}Copy the code

70. Climbing stairs (exactly the same dynamic equation as Fibonacci number)

 public int climbStairs(int n) {
     if(n<3)returnn; Int dp[]=new int[n+1]; Dp [1]=1; dp[1]=1; dp[1]=1; Dp [2]=2; dp[2]=2;for(int i=3; i<=n; N {dp[I]=dp[i-1]+dp[i-2]; }return dp[n];
 }
Copy the code

class Solution{
    public int climbStairs(int n){
        if(n<3)returnn; Int dp[]=new int[n]; Dp [0]=1; dp[0]=1; Dp [1]=2; dp[1]=2;for(int i=2; i<n; N {dp[I]=dp[i-1]+dp[i-2]; }returndp[n-1]; }}Copy the code

class Solution {
    public int climbStairs(int n) {
       if(n<=3) returnn; Int dp1=1; int dp2=2;for(int i=3; i<=n; i++){ int temp=dp2; dp2 = dp2 + dp1; dp1=temp; }returndp2; // Just return an int, so we can get rid of the dp array}}Copy the code

class Solution {
    public int climbStairs(int n) {
       if(n<=3) returnn; Int dp1=1; int dp2=2;for(int i=3; i<=n; i++){ dp2 = dp2 + dp1; dp1 = dp2 - dp1; // Add dp1 from dp2 to dp1.returndp2; // Just return an int, so we can get rid of the dp array}}Copy the code

746. Climb stairs at minimal cost

The most obvious of these is greedy, but it’s dynamic programming, because you can choose to go up one ladder or up two

Each subscript of the array is a ladder, and the ith ladder corresponds to a non-negative cost cost[I] (the subscript starts at 0).

You spend stamina every time you climb a ladder, and once you pay stamina, you can choose to climb one ladder or two (dynamic programming).

Please find the lowest cost to reach the top of the floor. At the beginning, you can choose to start with an element with subscript 0 or 1 as the initial ladder (supplementary condition).

Example 1:

Input: cost = [10, 15, 20] Output: 15 Explanation: The lowest cost is to start at cost[1] and then walk two steps to the top of the ladder, which costs 15 in total. Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] Output: 6 Explanation: The lowest cost is to start at cost[0], pass through the ones one by one, skip cost[3], and cost 6 altogether.

Now, the dp array is not the number of options, it’s the cost. Dp [I] is the minimum cost to get to the i-1 position. Dp [i-2] is the minimum cost to get to the i-2 position

Math. Min (dp[i-1]+cost[I], DP [i-2]+cost[I])

namely

Dp [I] = Math. Min (dp[i-1], dp[i-2])+cost[I]

Notice why I’m adding cos (I), not cos (I -1),cos (I -2), because they’re saying that every time you climb up a ladder you have to expend the corresponding amount of stamina. Cost [I] is the cost of getting to I from I minus one or I minus two, so of course it’s plus cost[I] here.

There are only two ways to get to I, either through i-1 or not through i-1. It’s a simple yes/no answer.

For loop order: because it is simulated step, and dp[I] and dp[i-1]dp[i-2] deduce, so it is ok to traverse cost array from front to back.

How about “at the beginning, you can choose to start with an element with subscript 0 or 1 as the initial ladder”? It doesn’t have to be a simulation, it just means to jump one step or two steps, and it costs cost[0] to jump one step from -1 to 0, and it costs cost[1] to jump two steps from -1 to 1.

Dynamic programming code:

class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp=new int[cost.length]; dp[0]=cost[0]; dp[1]=cost[1]; // Initialize??for(int i=2; i<cost.length; i++){ dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i]; } // we do not return dp[cost.length-1] directly, but take the least value of the penultimate step, the second stepreturnMath.min(dp[cost.length-1],dp[cost.length-2]); }}Copy the code

And since the array of t goes from 0 to n minus 1, the array of DP goes from 0 to n minus 1