Hot 100 dynamic programming

53. Maximum subarray and
    Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return 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 .

dp[] What is loaded in is the value of the current largest continuous subsequence , If the previous value is negative , Is the current dp[i] Load nums[i], Load on the contrary dp[i-1]+nums[i]

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
    
            if(dp[i-1] > 0){
    
                dp[i] = dp[i-1] + nums[i];
            }
            else{
    
                dp[i] = nums[i];
            }
        }
        for(int i = 0; i < dp.length; i++){
    
            max = Math.max(dp[i],max);
        }
        return max;
    }
}

62. Different paths
    A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）.

The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish” ）.

Ask how many different paths there are in total ？

dp[i][j] Express i That's ok j How many paths does the column have at most
dp[i][j] = dp[i-1][j] + dp[i][j-1]

class Solution {
    
    public int uniquePaths(int m, int n) {
    
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
    
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++){
    
            dp[0][i] = 1;
        }
        for(int i = 1; i < m; i++){
    
            for(int j = 1; j < n; j++){
    
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

139. Word splitting
     Give you a string s And a list of strings wordDict As a dictionary . Please judge whether you can use the words in the dictionary to splice s .

Be careful ： It is not required to use all the words in the dictionary , And the words in the dictionary can be reused .

For example, by the word applepen list=[apple,pen]
dp[i] To i Whether letters can form words
that ,dp[i] = dp[j] && check(j-i),dp[j] To j Can words be formed ,check From j To i Whether it appears in list in

class Solution {
    
    public boolean wordBreak(String s, List<String> wordDict) {
    
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = 1; i <= s.length(); i++){
    
            for(int j = 0; j < i; j++){
    
                dp[i] = dp[j] && wordDict.contains(s.substring(j,i));
                if(dp[i] == true){
    
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

198. raid homes and plunder houses
     You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm , The maximum amount that can be stolen overnight .

Example 1：

Input ：[1,2,3,1]
Output ：4
explain ： Steal 1 House No ( amount of money = 1) , And then steal 3 House No ( amount of money = 3).
Maximum amount stolen = 1 + 3 = 4 .

State transition equation ： dp[i] = Max(dp[i-2]+nums[i],dp[i-1])

279. Complete square
     Give you an integer n , return And for n The minimum number of complete squares of .

Complete square It's an integer , Its value is equal to the square of another integer ; let me put it another way , Its value is equal to the product of the self multiplication of an integer . for example ,1、4、9 and 16 They're all perfect squares , and 3 and 11 No .

Example 1：

Input ：n = 12
Output ：3
explain ：12 = 4 + 4 + 4

State transition equation ：dp[i] = Math.min(dp[i],dp[i-jj]+1);
dp[i] Express i The least square required , Traverse than i All small squares ,dp[i-jj]+1 Indicates if j Is the square number , The remaining number needs several squares . At the same time, add 1 Indicates that j.

300. The longest increasing subsequence
     Give you an array of integers nums , Find the length of the longest strictly increasing subsequence .

Subsequence Is a sequence derived from an array , Delete （ Or do not delete ） Elements in an array without changing the order of the rest . for example ,[3,6,2,7] It's an array [0,3,1,6,2,2,7] The subsequence .

Example 1：

Input ：nums = [10,9,2,5,3,7,101,18]
Output ：4
explain ： The longest increasing subsequence is [2,3,7,101], So the length is 4 .

dp[i] It's loaded with i For the longest increment subsequence at the end , Just find i Before , Than i Small number j, Compare dp[j]+1 Size , Find the maximum , Can be calculated dp[i] The maximum of . Finally from the dp Find the maximum in
dp[i] = Math.max(dp[i],dp[j]+1);

337. raid homes and plunder houses III
     The thief found a new area to steal . There is only one entrance to the area , We call it root .

except root outside , Each house has and only has one “ Father “ The house is connected to it . After some reconnaissance , The clever thief realized that “ All the houses in this place are arranged like a binary tree ”. If Two directly connected houses were robbed the same night , The house will alarm automatically .

Given a binary tree root . return Without triggering the alarm , The maximum amount a thief can steal .

Depth-first search , Return value [i,j] i Indicates the maximum value of the selected current node ,j Indicates that the maximum value of the current node is not selected
result[0] = root.val + left[1] + right[1];
result[1] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);

It should be noted that , Do not select the value of the current node , Need comparison left,right,0 and 1 Size , There may be two consecutive points that are not selected .

338. Bit count
     Give you an integer n , about 0 <= i <= n Each of the i , Calculate its binary representation 1 The number of , Returns a length of n + 1 Array of ans As the answer .

Example 1：

Input ：n = 2
Output ：[0,1,1]
explain ：
0 --> 0
1 --> 1
2 --> 10

n&(n-1) You can put n Last digit of 1 become 0, thus , as long as n>0, You can always calculate how many there are in this way 0

class Solution {
    
    public int[] countBits(int n) {
    
        int[] res = new int[n+1];
        for(int i = 0; i < n+1; i++){
    
            res[i] = ones(i);
        }
        return res;
    }
    public int ones(int n){
    
        int res = 0;
        while(n > 0){
    
            n &= (n-1);
            res++;
        }
        return res;
    }
}

416. To divide into equal and subsets
     To give you one Contains only positive integers Of Non empty Array nums . Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .

Example 1：

Input ：nums = [1,5,11,5]
Output ：true
explain ： Arrays can be divided into [1, 5, 5] and [11] .

01 A variant of the backpack ,dp[i][j] ,i Express nums,j From 0 To target
State transition equation ：
if(nums[i] > j){
dp[i][j] = dp[i-1][j];
continue;
}
if(nums[i] == j){
dp[i][j] = true;
continue;
}
if(nums[i] < j){
dp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j];
}

class Solution {
    
    public boolean canPartition(int[] nums) {
    
        
        int sum = 0;
        for(int num: nums){
    
            sum+=num;
        }
        if(sum%2 == 1){
    
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length][target+1];
        for(int i=0; i < target+1; i++){
    
            if(nums[0] == i){
    
                dp[0][i] = true;
                continue;
            }
            dp[0][i] = false;
        }
        for(int i = 1; i < nums.length; i++){
    
            for(int j = 0; j < target+1; j++){
    
                if(nums[i] > j){
    
                    dp[i][j] = dp[i-1][j];
                    continue;
                }
                if(nums[i] == j){
    
                    dp[i][j] = true;
                    continue;
                }
                if(nums[i] < j){
    
                    dp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j];
                }
            }
        }
        return dp[nums.length-1][target];
    }
}

647. Palindrome string
     Give you a string s , Please count and return this string Palindrome string Number of .

Palindrome string Is reading the same string as reading it backwards .

Substring Is a sequence of consecutive characters in a string .

A substring with different start or end positions , Even if it's made up of the same characters , It's also seen as a different substring .

dp[i][j] Represents a string from i To j Is it palindrome
If j-i0( Single character ), It must be
If j-i1( Two characters ), If s[i]==s[j], It's also
If j-i>=2( Three or more ), Zhao Dapeng dp[i+1][j-1], If it is true, also s[i] == s[j], So it is
It should be noted that , When traversing , You can't 【0,1】【0,2】【0,3】 This way , need 【03】【1,3】,【2,3】【3,3】 This way

class Solution {
    
    public int countSubstrings(String s) {
    
        int length = s.length();
        int res = 0;
        boolean[][] dp = new boolean[length][length];
        for(int j = 0; j < length;j++){
    
            for(int i = 0; i<=j; i++){
    
                if(j-i == 0){
    
                    dp[i][j] = true;
                    res++;
                    continue;
                }
                if(j-i == 1){
    
                    if(s.charAt(i) == s.charAt(j)){
    
                        dp[i][j] = true;
                        res++;
                        continue;
                    }
                }
                if(j-i > 1){
    
                    if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1]){
    
                        dp[i][j] = true;
                        res++;
                        continue;
                    }
                }

            }
        }
        return res;
    }

}