Three questions LeetCode | introduction to dynamic programming

Climb the stairs

Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? Note: given n is a positive integer.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building.

1. 1 order plus 1 order
2. 2 order

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building.

1. 1 order plus 1 order plus 1 order
2. 1 order plus 2 order
3. 2 order plus 1 order

Their thinking

This is the simplest problem in dynamic programming. I remember seeing this problem for the first time in the blue bridge cup exercise. Although this is an introduction to dynamic programming, I will not give you any written definition of a dynamic programming algorithm. This is because the concept of dynamic programming is still very complicated, and you’ll be scared of dynamic programming when you look at the ideas and characteristics of dynamic programming algorithms. As for the definition of dynamic programming, I just want to say that it is a global optimal solution. Global means dynamic programming is all things considered. Without further ado, let’s start with the solution.

So in this case, we see that there’s only one way to climb one ladder, and two ways to climb two stairs. Then we can see that there are three ways to climb three steps, because climbing three steps is equal to climbing one step on top of climbing two steps. Similarly, climbing 4 steps is equal to climbing 1 and 2 steps on the basis of 3;

This idea of “standing on the shoulders of giants” is the idea of dynamic programming.

The implementation code

The first thing we can think of is using recursion. The recursion is the exact opposite of what we did above. The recursive idea is that the number of ways you can climb n stairs is equal to the number of times you can climb n minus 1 stairs plus the number of times you can climb n minus 2 stairs. However, the recursive method does not save the results of the calculation, resulting in many repeated calculations, so timeouts are inevitable.

1. The recursion

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        return climbStairs(n-1)+climbStairs(n-2); }}Copy the code

Run result: timeout

2. Dynamic planning

The whole idea of dynamic programming is very similar to recursion, but saves the results through a DP array. It’s going to be a lot faster.

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

The maximum sum of contiguous subarrays

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example 1:

Input: nums = [– 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.

Example 2:

Input: nums = [1] Output: 1

Example 3:

Input: nums = [0] Output: 0

Example 4:

Input: nums = [-1] Output: -1

Example 5:

Input: nums = [-100000] Output: -100000

Tip:

1 <= nums.length <= 3 * 104 -105 <= nums[i] <= 105  

Step up: If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.

Their thinking

Dynamic programming is the optimal solution to this problem. The idea of dynamic programming is also clear. Given an array [-2,1], we can see that the sum of the numbers [-2,1] is smaller than the second element of the array,1. So the maximum sum of a continuous subarray is 1. When the array becomes [-2,1,-3], we already know that the maximum sum of the contiguous subarrays in [-2,1] is 1. So 1 is larger than [-3], so the maximum sum of the contiguous subarrays of this array is still 1.

In short, each time an element is added to an array, it is compared with the maximum sum of the contiguous subarray of the array before it is added. The larger sum is the maximum sum of the contiguous subarray of the new array. The code implementation is as follows:

The implementation code

class Solution {
    public int maxSubArray(int[] nums) {
        int dp[]=new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1; i<dp.length; i++){//compare the num last status plus current num and current num 
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            //compare max and dp[i],it will update max
            max=Math.max(max,dp[i]);
        }
        returnmax; }}Copy the code

Iii. Game currency combination

COINS. Given an unlimited number of coins with values of 25 cents, 10 cents, 5 cents, and 1 cent, there are several ways to write code to calculate n cents. (The result may be large, you need to mold the result to 1000000007)

Example 1:

Input: n =5 Output: 2 Explanation: There are two ways to get the total amount: 5=5 5=1+1+1+1+1

Example 2:

Input: n = 10 output: 4: there are four ways to gather together Adrian rodriguez huber -) fernando amount: 10 = 10 10 = 5 + 5 = 5 + 1 + 1 + 1 + 1 + 10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Description:

Note:

You can assume:

0 <= n (total amount) <= 1000000

Their thinking

It’s a little hard to see what the transition equation is, but let’s make a table and see if we can see any patterns.

So let’s first define an array of dp’s and an array of all coins

 int[] dp = new int[n + 1];
 int[] coins = {1.5.10.25};
Copy the code

And set dp[0]=1 as the boundary condition, as perfect can be represented by a coin is 1. Dp [I]+=dp[i-coin] When i-coin is 0, the result is 1, indicating the situation that a coin can represent.

We can simply derive the state transition equation

// The result is required to be modulo 1000000007
dp[i] = dp[i] + dp[i - coin] 
Copy the code

Code implementation

class Solution {
    public int waysToChange(int n) {
       int dp[]=new int[n+1];
       int coins[]={1.5.10.25};
       dp[0] =1;

        for(int coin : coins) {
            for(int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007; }}returndp[n]; }}Copy the code