May training (day 28) - Dynamic Planning

Preface

The content of today's algorithm is ： Dynamic programming

One 、 climb stairs

         Suppose you're climbing the stairs . need n rank You can reach the roof . Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？

Example 1：
Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .
Example 2：

Input ：nums = [1]
Output ：1
Example 3：

Input ：nums = [5,4,-1,7,8]
Output ：23

One 、 Ideas :

        （1） If it is below the third order, you can return directly
        （2） If it is more than the third order, the current state is the sum of the previous two states , loop n Time ;

Two 、 Source code

class Solution {
    
public:
    int climbStairs(int n) {
    
        int a=1,b=2,c=0;
        
        if(n<3) return n;

        for(int i=3 ;i<=n ;i++){
    
                c=a+b;
                a=b;
                b=c;
        }
        return c;
    }
};

3、 ... and . Knowledge point

         Fibonacci sequence

Two 、 Maximum subarray and

         Give you an array of integers nums , Please find one with The continuous subarray of the largest sum （ A subarray contains at least one element ）, Back to its Maximum and .
Subarray Is a continuous part of the array .

Example 1：

Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .
Example 2：

Input ：nums = [1]
Output ：1
Example 3：

Input ：nums = [5,4,-1,7,8]
Output ：23

One 、 Ideas :

        （1） The past state is added to the next state and Compare with the next state , Contrast out At its best
        （2） Compare the best status recorded in the past with the current status , Choose the best
        （3） It suddenly occurred to me why Status meeting Time changes ？ That's because the state will change with the number of cycles and add to the next state , May become weak , It may also get stronger

Two 、 Source code

class Solution {
    
public:
    int maxSubArray(vector<int>& nums) {
    
        int max=-1000000,now=0;
        
        for(int i=0;i<nums.size();i++){
    
            now=now+nums[i] > nums[i]?now+nums[i]:nums[i];
            max=max > now?max:now;
        }
        return max;
    }
};

// for the first time   Overtime spicy   Code 

class Solution {
    
public:
    int maxSubArray(vector<int>& nums) {
    
        int sum=0,max=-100000;
        int len=nums.size();

        for(int i=0 ;i<len ;i++){
    
            for(int j=i ;j<len ;j++){
    
                sum+=nums[j];
                if(sum > max){
    
                    max=sum;
                }        
            }

            sum=0;
        }
        return max;
    }
};

3、 ... and . Knowledge point

         Dynamic programming