DP question brushing record

Just for the record , Some pictures can be pasted by themselves gitee Website view , Just need a password … Forget it

One 、 Dynamic programming

The original problem can be decomposed into two smaller subproblems , And the solution of subproblem can be reused

2022.1.18 Fibonacci

One 、 The finger of the sword Offer 10- I. Fibonacci sequence

Write a function , Input n , Fibonacci, please （Fibonacci） The number of the sequence n term （ namely F(N)）. Fibonacci series is defined as follows ：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), among N > 1.
The Fibonacci series is composed of 0 and 1 Start , The Fibonacci number after that is the sum of the two numbers before .

The answer needs to be modelled 1e9+7（1000000007）, If the initial result of calculation is ：1000000008, Please return 1.

/** * @param {number} n * @return {number} */
var fib = function(n) {
    
    //  violence 
    // const MOD = 1e9+7;
    // if(n === 0) return 0;
    // if(n === 1 || n === 2) return 1;
    // return (fib (n-1) + fib (n-2))%MOD;

    // //  With memo DP, Time complexity  O(n)
    // if(n === 0) return 0;
    // const arr = new Array(n+1);
    // return dp(arr, n);

    // dp Iterations of arrays 
    const MOD = 1e9+7;
    if(n < 2) return n;
    if(n==2) return 1;
    const dp = new Array(n+1);
    dp[1] = dp[2] = 1;
    for(let i = 3; i <= n; i++){
    
        dp[i] = (dp[i-1] +dp[i-2])%MOD;
    }
    return dp[n];
};

// const dp =(arr, n) =>{
    
// const MOD = 1e9+7;
// if(n == 1 || n == 2) return 1;
// if(arr[n] != 0) return arr[n];
// arr[n] = (dp(arr, n-1) + dp(arr, n-2))%MOD;
// return arr[n];
// }

//  Problem solving time complexity O(1)
//  State compression , from N Reduce to 2
var fib = function(n) {
    
    const MOD = 1000000007;
    if (n < 2) {
    
        return n;
    }
    let p = 0, q = 0, r = 1;
    for (let i = 2; i <= n; ++i) {
    
        p = q; 
        q = r; 
        r = (p + q) % MOD;
    }
    return r;
};

Two 、 509. Fibonacci number

Fibonacci number , Usually use F(n) Express , The sequence formed is called Fibonacci sequence . The sequence is composed of 0 and 1 Start , Each of the following numbers is the sum of the first two numbers . That is to say ：

```
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2), among  n > 1
```

 Here you are.  `n` , Please calculate  `F(n)` . 

2022.1.19

One 、 322. Change for

Give you an array of integers coins , Coins of different denominations ; And an integer amount , Represents the total amount .

Calculate and return the amount needed to make up the total amount The minimum number of coins . If no combination of coins can make up the total amount , return -1 .

You can think of the number of coins of each kind as infinite .

cccccccccccccccccccccc

Two 、

2022.1.20

One 、 674. The longest continuous increasing sequence

Given an unordered array of integers , Find the longest and Successive increasing subsequences , And return the length of the sequence .

Successive increasing subsequences It can be made up of two subscripts l and r（l < r） determine , If for each l <= i < r, There are nums[i] < nums[i + 1] , So the subsequence [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] It's a continuous increasing subsequence .

/** * @param {number[]} nums * @return {number} */
var findLengthOfLCIS = function(nums) {
    
   let ans = 0;
   let start = 0;
    for(let i = 0 ; i < nums.length; i++){
    
        if(i>0 && nums[i] <= nums[i-1])
            start = i;
        ans = Math.max(ans, i - start + 1);
    }
    return ans;
};

Two 、 300. The longest increasing subsequence

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

Subsequences are sequences derived from arrays , 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 .

2-1 Dynamic programming

/** * @param {number[]} nums * @return {number} */
var lengthOfLIS = function(nums) {
    
    //  Yes dp The array is initialized to 1
    const numsLen = nums.length;
    const dp = new Array(numsLen).fill(1);
    for(let  i= 0;i < numsLen;i++){
    
        for(let j =0;j<i;j++){
    
            if(nums[i] > nums[j]){
    
                // dp[i] It's stored with nums[i] Is the number of longest increasing subsequences of the maximum 
                dp[i] = Math.max(dp[i],dp[j]+1);
            }
        }
    }
    let max = 1;
    for(key in dp){
    
        max = Math.max(dp[key],max);

    }
    return max;
};

2-2 Binary search

Normal people can't imagine , What's more? , I am still an ordinary person

2022.1.24 Two dimensional increasing subsequence ： Envelope nesting problem

One 、 354. The envelope problem of Russian Dolls

Here's a two-dimensional array of integers envelopes , among envelopes[i] = [wi, hi] , It means the first one i The width and height of each envelope .

When the width and height of another envelope are larger than this one , This envelope can be put into another envelope , Like Russian Dolls .

Please calculate How many at most Envelopes can form a group “ Russian Dolls ” The envelope （ You can put one envelope in another ）.

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-mFODkLA1-1645370197776)(https://gitee.com/hannah_bingo/yyy/raw/master/image-20220124111602343.png)]

/** * @param {number[][]} envelopes * @return {number} */

 //  Time complexity O(n Fang )
var maxEnvelopes = function(envelopes) {
    
    const enLen = envelopes.length;

    if(enLen === 0){
    
        return 0;
    }
    //  Two dimensional array arr[i][0] Ascending order ,arr[i][1] Descending 
    envelopes.sort((arr1, arr2) =>{
    
        return arr1[0] !== arr2[0] ? arr1[0] - arr2[0] : arr2[1] - arr1[1];
    })

    //  lookup arr[i][1] Of LIS
    let max = 1;
    
    // const dp = new Array[enLen].fill(1);
    const dp = new Array(enLen).fill(1);
    for(let i = 1; i<enLen; ++i){
    
        for(let j = 0 ; j<i;++j){
    
            if(envelopes[i][1] > envelopes[j][1]) {
    
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        max = Math.max(max, dp[i]); 
    }
    return max;
};

Two 、 673. The number of longest increasing subsequences

Details

var findNumberOfLIS = function(nums) {
    
    let n = nums.length, maxLen = 0, ans = 0;
    const dp = new Array(n).fill(0);
    const cnt = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
    
        dp[i] = 1;
        cnt[i] = 1;
        for (let j = 0; j < i; ++j) {
    
            if (nums[i] > nums[j]) {
    
                if (dp[j] + 1 > dp[i]) {
    
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j]; //  Reset count 
                } else if (dp[j] + 1 === dp[i]) {
    
                    cnt[i] += cnt[j];
                }
            }
        }
        if (dp[i] > maxLen) {
    
            maxLen = dp[i];
            ans = cnt[i]; //  Reset count 
        } else if (dp[i] === maxLen) {
    
            ans += cnt[i];
        }
    }
    return ans;
};

2022.1.26

One 、 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 .

/** * @param {number[]} nums * @return {number} */
var maxSubArray = function(nums) {
    
    const numsLen = nums.length;
    const dp = new Array(numsLen);
    let max = -Infinity;
    for(let i =0; i< numsLen;i++){
    
        if(i>0){
    
            dp[i] = (dp[i-1]+nums[i]) > nums[i] ? (dp[i-1]+nums[i]) : nums[i];
        }else dp[0] = nums[0];
        max = Math.max(max, dp[i]);
    }
    return max;
};

2022.2.10

One 、1143. Longest common subsequence

Given two strings text1 and text2, Returns the longest of these two strings Common subsequence The length of . If it doesn't exist Common subsequence , return 0 .

A string of Subsequence This is a new string ： It is to delete some characters from the original string without changing the relative order of the characters （ You can also delete no characters ） After the composition of the new string .

for example ,“ace” yes “abcde” The subsequence , but “aec” No “abcde” The subsequence .
Two strings of Common subsequence Is the subsequence shared by these two strings .

/** * @param {string} text1 * @param {string} text2 * @return {number} */
var longestCommonSubsequence = function(text1, text2) {
    
    const t1L =  text1.length,t2L = text2.length;
    // base case
    const dp = new Array(t1L + 1).fill(0).map(() => new Array(t2L + 1).fill(0));
    //  State shift 
    //  Positive traversal 
    for(let i = 1; i <= t1L; i++){
    
        for(let j = 1; j<=t2L; j++){
    
            if(text1[i-1] === text2[j-1]){
    
                dp[i][j] = dp[i-1][j-1] +1;
            }else{
    
                dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
            }
        }
    }
    return dp[t1L][t2L];
};

Two 、 72. Edit distance

Here are two words for you word1 and word2, Please return to word1 convert to word2 The minimum number of operands used .

You can do the following three operations on a word ：

Insert a character
Delete a character
Replace a character

/** * @param {string} word1 * @param {string} word2 * @return {number} */
 //  Overtime 
// var minDistance = function(word1, word2) {
    
// const len1 = word1.length;
// const len2 = word2.length;

// const dp = (i,j) =>{
    
// // base case
// // word1 Change to the end first 
// if(i===-1) return j+1;
// // word2  Go to the end first , Delete word1 remainder  
// if(j===-1) return i+1;

// //  choice 
// if(word1[i] === word2[j]){
    
// return dp(i-1,j-1);
// } else {
    
// return Math.min(
// dp(i,j-1) + 1, //  Insert 
// dp(i -1 ,j) + 1, //  Delete 
// dp(i-1,j-1) + 1 //  Replace 
// )
// }
// } 
// return dp(len1-1,len2-1);
// };

//  Memo optimization 
var minDistance = function(word1, word2) {
    
    const w1L = word1.length;
    const w2L = word2.length;
    //  Memorandum 
    let memo = new Array(w1L+1).fill(-1).map(() => new Array(w2L+1).fill(-1));
    const dp = (i,j) => {
    
             // base case
        // w1,w2 Walk the 
       
         if (i === -1) return j+1;
        if (j === -1) return i+1;
        //  Check the memo first 
        if(memo[i][j] !== -1) return memo[i][j];
   

        if(word1[i] === word2[j]){
    
            memo[i][j] = dp(i-1,j-1);
        } else{
    
            memo[i][j] = Math.min(
                dp(i-1,j) + 1,  //  Delete 
                dp(i,j-1) + 1,  //  Insert 
                dp(i-1,j-1)+1
            )
        }
        return memo[i][j];
    }
    return dp(w1L-1,w2L-1);
};

// DP Table
// var minDistance = function (word1, word2) {
    
// let dp = Array.from(Array(word1.length + 1), () =>
// Array(word2.length + 1).fill(0)
// );
// /* base case  yes i Walk the word1 or j Walk the word2, You can directly return the remaining length of another string  */
// // j Walk the word2  If i It's not over yet word1, Then you can only delete word1 Shorten to word2, That is, directly return the remaining length of another string 
// for (let i = 1; i <= word1.length; i++) {
    
// dp[i][0] = i;
// }
// //  Empathy   If i Walk the word1 when j I haven't finished yet word2, Then you can only insert word2 Insert all the remaining characters word1
// for (let j = 1; j <= word2.length; j++) {
    
// dp[0][j] = j;
// }

// for (let i = 1; i <= word1.length; i++) {
    
// for (let j = 1; j <= word2.length; j++) {
    
// if (word1[i - 1] === word2[j - 1]) {
    
// //  Do nothing 
// dp[i][j] = dp[i - 1][j - 1];
// } else {
    
// //  Choose one of three   Which operation results in the smallest editing distance , Choose who 
// dp[i][j] = Math.min(
// //  Delete 
// //  Put... Directly word1[i] Delete this character , Move forward i Keep following j contrast   Operands +1
// dp[i - 1][j] + 1,
// //  Insert 
// //  Directly in word1[i] Insert a and word2[j] Same characters , that word2[j] Is matched , Move forward j Keep following i contrast 
// dp[i][j - 1] + 1,
// //  Replace 
// //  Put... Directly word1[i] Replace with word2[j]  So the two match , Move forward at the same time i,j Continue to contrast 
// dp[i - 1][j - 1] + 1
// );
// }
// }
// }

// return dp[word1.length][word2.length];
// };

2022.2.12

One 、 516. The longest palindrome subsequence

Give you a string s , Find the longest palindrome subsequence , And return the length of the sequence .

Subsequence is defined as ： Without changing the order of the remaining characters , A sequence formed by deleting some characters or not deleting any characters .

/** * @param {string} s * @return {number} */
var longestPalindromeSubseq = function(s) {
    
    const sL = s.length;
    const dp = new Array(sL+1).fill(0).map(() => new Array(sL+1).fill(0));
    // base case
    for(let i = 0; i < sL; i++){
    
        dp[i][i] = 1;
    }

    //  State shift , Reverse traversal , seek dp[0][j]
    for(let i = sL-2; i >= 0; i--){
    
        for(let j = i+1;j<sL;j++){
    
            if(s[i] === s[j]){
    
                dp[i][j] = dp[i+1][j-1] + 2;
            }else {
    
                dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
            }
        }
    }
    return dp[0][sL -1];

};

CCCCCCCCC, There are some strange problems in debugging

Two 、 The longest text string

Give you a string s, find s The longest palindrome substring in

class Solution {
    
   public String longestPalindrome(String s) {
    
    int n = s.length();
    String res = "";
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
    
        for (int j = i; j < n; j++) {
    
            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i  Represents the length minus  1 
            if (dp[i][j] &&  j - i + 1 > res.length()) {
    
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}

}

3、 ... and 、 1312. The minimum number of inserts to make a string a palindrome string

Give you a string s , You can insert any character in any position of the string every time .

Please return to let s To become a palindrome Minimum number of operations .

/** * @param {string} s * @return {number} */
var minInsertions = function(s) {
    
    const sL = s.length;
        const dp = new Array(sL+1).fill(0).map(()=>new Array(sL+1).fill(0));
        // base case i==j when dp[i][j]=0
        //  State shift , Obliquely ergodic 
        for(let i = sL-2; i >= 0; i--){
    
            for(let j = i+1; j <sL; j++){
    
                if(s[i] === s[j]){
    
                    dp[i][j] = dp[i+1][j-1]; 
                } else {
    
                    //  Choose the least expensive insert 1
                    dp[i][j] = Math.min(dp[i+1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[0][sL-1];

};

Four 、 10. Regular Expression Matching

Interview questions 19. Regular Expression Matching

Please implement a function to match the contains ’. ‘ and ’‘ Regular expression of . Characters in pattern ’.‘ Represents any character , and ’' Indicates that the character in front of it can appear any number of times （ contain 0 Time ）. In the subject , Matching means that all characters of a string match the whole pattern . for example , character string "aaa" With the model "a.a" and "abaca" matching , But with "aa.a" and "ab*a" No match .

/** * @param {string} s * @param {string} p * @return {boolean} */
var isMatch = function(s, p) {
    
    const sL = s.length;
    const pL = p.length;
    
    dp = (s,i,p,j) => {
    
        // base case,s and p It's over 
        if(j === pL) {
    
            return i === sL;
        } else if (i === sL){
    
            //  Matching rules are not finished --->
            //  The rest is not  a* 
            if((pL - j)%2 === 1 ){
    
                return false;
            }
            //  The remaining x*y*z*
            while(j+1 < pL){
    
                if(p[j+1] != '*'){
    
                    return false;
                }
                j += 2;
            }
            return true;
        }

        let res = false;
        //  State shift 
        //  matching 
        if(s[i] === p[j] || p[j] === '.'){
    
            if(j<pL-1 && p[j+1] === '*'){
    
                //  matching 0 Or many times 
                res =  dp(s,i,p,j+2) || dp(s,i+1,p,j);
            } else {
    
                //  Normal match 
                res = dp(s,i+1,p,j+1);
            }
        }
        else {
    
            //  matching 0 Time 
            if(j < pL-1 && p[j+1] === '*'){
    
                res = dp(s,i,p,j+2);
            } else {
    
                res = false;
            }
        }
    
        return res;
    }
    dp(s,0,p,0);
};

• If I'm guilty , Please don't let me check the code ten times ,undefined,undefined,undefined,undefined,undefined…
• wacaowocao--------------------------------------------------------- Wow, wow, wow

5、 ... and 、 887. Eggs fall

Here you are. k The same egg , And you can use a building from 1 Layer to tier n There are layers in total n A building on the ground floor .

There are known floors f , Satisfy 0 <= f <= n , Any from higher than f All the eggs that fall from the floor will be broken , from f The eggs that fall from the floor or the lower floor will not break .

Every operation , You can take an unbroken egg and take it from any floor x Throw down （ Satisfy 1 <= x <= n）. If the egg breaks , You can't use it again . If an egg is not broken after being dropped , Then you can in subsequent operations Reuse This egg .

Please calculate and return to confirm f The exact value Of Minimum number of operations How much is the ？

// /**
// * @param {number} k
// * @param {number} n
// * @return {number}
// */
// //  Recursion timeout 
// var superEggDrop = function(k, n) {
    
// const memo = new Map();
// function dp (k, n) {
    
// if (k === 1) return n; //  When k by 1 when , Only all floors can be scanned linearly 
// if (n === 0) return 0;
// if (memo.has(k + '' + n)) {
    
// return memo.get(k + '' + n)
// }
// let res = Infinity;
// for (let i = 1; i <= n; i++) {
    
// res = Math.min(
// res,
// Math.max(
// dp(k, n - i),
// dp(k - 1, i - 1)
// ) + 1
// )
// }
// memo.set(k + '' + n, res)
// return res;
// }
// return dp(k, n)
// };

var superEggDrop= function(k, n) {
    
    const dp = new Array(k + 1).fill(0).map(() => new Array(n + 1).fill(0));
    let m = 0;
    while (dp[k][m] < n) {
    
        m++;
        for (let i = 1; i <= k; i++) {
    
            dp[i][m] = dp[i][m - 1] + dp[i - 1][m - 1] + 1;
        }
    }
    return m;
};

2022.2.15

Chapter one knapsack problem

1-1 0-1 knapsack problem

One 、 474. One and zero

Here's an array of binary strings strs And two integers m and n .

Please find out and return to strs Length of the largest subset of , This subset most Yes m individual 0 and n individual 1 .

If x All of the elements of are also y The elements of , aggregate x Is a collection y Of A subset of .

/** * @param {string[]} strs * @param {number} m * @param {number} n * @return {number} */

//0-1 knapsack 
var findMaxForm = function(strs, m, n) {
    
    // m,n As a backpack W and N
    // dp[i][j]  Express   about   And then there were i individual 0 and j individual 1 , In this case  strs  The largest subset of   The length of 
    const dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0));
    // base case
    // for(let i = 0; i < m;i++){
    
    // dp[i][0] = 0;
    // }
    // for(let j = 0; j < n; j++){
    
    // dp[0][j] = 0;
    // }

    for(let p= 0; p < strs.length; p++){
    
        let zeroNum = 0,oneNum = 0;
        const str = strs[p];
        for(let s = 0; s <str.length;s++ ){
    
            console.log(str[s]);
            if(str[s] === '0') ++zeroNum;
            else ++oneNum;
        }
        for(let i = m; i >= zeroNum; i--){
    
            for(let j = n; j >= oneNum; j--){
    
                dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum] + 1);
            }
        }
         
    }
     return dp[m][n];
  
};

Two 、 494. Objectives and

Give you an array of integers nums And an integer target .

Add... Before each integer in the array ‘+’ or ‘-’ , And then concatenate all the integers , You can construct a expression ：

for example ,nums = [2, 1] , Can be in 2 Before adding ‘+’ , stay 1 Before adding ‘-’ , And then concatenate them to get the expression “+2-1” .
Returns the 、 The result is equal to target Different expression Number of .

3、 ... and 、 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 .

/** * @param {number[]} nums * @return {boolean} */
var canPartition = function(nums) {
    
    // 
    let sum = 0;
    nums.forEach(item => sum += item);
    if(sum %2 !== 0) return false;

    // dp[i][i] :  For the former i Items , Whether it can be filled with a capacity of j;
    const dp = new Array(nums.length+1).fill(0).map(()=>new Array(sum / 2 +1) );
    // base case
    for(let i = 0; i< nums.length;i++){
    
        dp[i][0] = true;
    }
    //  Status installation I 
    for(let i = 1; i<= nums.length;i++){
    
        for(let  j =1 ;j <= sum /2;j++){
    
            if(j-nums[i-1] <0){
    
                dp[i][j] = dp[i-1][j];
            }else {
    
                dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
            }
        }
    }

    //  seek dp[nums.length-1][sum/2];
    return dp[nums.length][sum/2];
};

The state of mind is fried

Four 、1049. The weight of the last stone II

I won't ！！ this TM How does the solution feel like a subset of knapsack solutions ？？？

1-2-14-3 Completely backpack problem

One 、[bug]322. Change for

Give you an array of integers coins , Coins of different denominations ; And an integer amount , Represents the total amount .

Calculate and return the amount needed to make up the total amount The minimum number of coins . If no combination of coins can make up the total amount , return -1 .

You can think of the number of coins of each kind as infinite .

/** * @param {number[]} coins * @param {number} amount * @return {number} */


var coinChange = function(coins, amount) {
    
    // dp[i][j] :  For the former i A coin , The capacity of the backpack is j when , The minimum number of coins required to fill a backpack 
    const dp = new Array(coins.length +1).fill(0).map(()=>new Array(amount+1).fill(0));
    // base case

    //  State shift 
    for(let i = 1; i <= coins.length;++i){
    
        for(let j = 1; j<=amount;++j){
    
            if(j-coins[i-1] < 0){
    
                dp[i][j] = dp[i-1][j];
            } else{
    
                dp[i][j] = Math.min(dp[i-1][j-coins[i-1]]+1 ,dp[i][j-coins[i-1]]+1);
            }
        }
    }
    // seek  dp[coins.length][amout]

  return dp[coins.length][amount];
};

Two 、 518. Change for II

Give you an array of integers coins Coins of different denominations , Give another integer amount Represents the total amount .

Please calculate and return the number of coin combinations that can be rounded up to the total amount . If no combination of coins can make up the total amount , return 0 .

Suppose that there are infinite coins of each denomination .

The subject data ensure that the results meet 32 Bit signed integer

/** * @param {number} amount * @param {number[]} coins * @return {number} */
var change = function(amount, coins) {
    
// dp[i][j] :  For the former i A coin , The capacity of the backpack is j when , Yes dp[i][j] A method of making up 
    const dp = new Array(coins.length +1).fill(0).map(()=>new Array(amount+1).fill(0));
    // base case
    for(let  i = 0; i <= coins.length;i++){
    
        dp[i][0] = 1;
    } 
    //  State shift 
    for(let i = 1; i <= coins.length;++i){
    
        for(let j = 1; j<=amount;++j){
    
            if(j-coins[i-1] < 0){
    
                dp[i][j] = dp[i-1][j];
            } else{
    
                dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
            }
        }
    }
    // seek  dp[coins.length][amout]

  return dp[coins.length][amount];
};