This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Two days ago (actually seven days ago), we talked about initial dynamic programming, dynamic programming by climbing stairs, portal -># Dynamic programming by climbing stairs. In this chapter, we are going to consolidate our learning with three strength buttons of medium difficulty. Without further ado, let’s begin

Sword refers to Offer II 103. Minimum number of coins

Tip:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

Answer key:

Determine the recursive state and derive the recursive equation: dp(x) = y. Y is the value, the minimum number of coins, and the number is related to the amount, so x is the amount. X can disaggregate DP (I) + 1, where DP (I) represents an amount less than X plus a coin in a coin. Coin (I)+1 can be converted into min(DP (I1)+ coins(J1), dp(I2)+ conins(j2)… , dp (in) + COINS (Jacqueline Nottingham)).

Code:

/ * * *@param {number[]} coins
 * @param {number} amount
 * @return {number}* /
var coinChange = function (coins, amount) {
    const n = amount + 1;
    const dp = new Array(n).fill(-1);

    // Boundary conditions
    dp[0] = 0;

    for (let i = 1; i < n; i++) {
        for (let k of coins) {
            let j = i - k;
            // The amount is smaller than the current coin amount
            if (i < k) continue;
            // j amount has no validity
            if (dp[j] === -1) continue;
            // If the previous value is invalid or the previous value is larger than the current j value +1, replace it with the current smaller value
            if (dp[i] === -1 || dp[i] > dp[j] + 1) dp[i] = dp[j] + 1; }}return dp[amount]
};
Copy the code

152. Maximum subarray of product

Answer key:

Normally, dp of x is equal to y, and y is the maximum value of the product to the x position. Dp (x) = min(dp(x-1) * val(x), val(x)). But if we have a negative number here, if we have a negative number dp of x minus 1, that’s going to be the minimum, and a negative number dp of x minus 1, that’s going to be the maximum of x. So here we need to define two numbers, iMax, the maximum to I, and iMin, the minimum. And then you can decide whether you want to multiply the maximum or the minimum based on whether your current x position is negative or positive.

The code is as follows:

/ * * *@param {number[]} nums
 * @return {number}* /
var maxProduct = function (nums) {
    IMax = iMin = 1, dp[0] = nums[0]
    let ans = -Infinity, iMax = 1, iMin = 1;

    for (let i = 0; i < nums.length; i++) {
        // If the value is negative, switch the maximum and minimum values
        if (nums[i] < 0) {
            const temp = iMax;
            iMax = iMin;
            iMin = temp;
        }
        / / Max
        iMax = Math.max(nums[i] * iMax, nums[i]);
        / / the minimum
        iMin = Math.min(nums[i] * iMin, nums[i]);
        
        ans = Math.max(iMax, ans);
    }
    return ans;
};
Copy the code

300. Longest increasing subsequence

Answer key:

Strictly increasing subsequences represent subsequences from smallest to largest in an array.

We find the recursive state, dp(x) = y, where y represents the longest increasing subsequence length to I, plus the longest increasing subsequence length to the last position I and the previous position with a value less than val(I) + 1.

So we get the state transition equation: dp(I) = DP (j) + 1&&j < I &&val (j) < val(I)

The code is as follows:

/ * * *@param {number[]} nums
 * @return {number}* /
var lengthOfLIS = function (nums) {
    const n = nums.length;
    // The minimum increment subsequence for each I position must be 1, and after initialization dp[0] = 1
    const dp = new Array(n).fill(1);
    let ans = 1;
    for (let i = 1; i < n; i++) {
        // Iterate over the element before position I to find the legal increasing subsequence
        for (let j = 0; j < i; j++) {
            // The value of the j position must be less than the value of the I position
            if (nums[j] < nums[i]) {
                // dp[I] is equal to the maximum of the increasing subsequence length +1 for all j positions.
                dp[i] = Math.max(dp[j] + 1, dp[i])
            }
        }
        // ans is equal to the maximum length of all increasing subsequences ending in I
        ans = Math.max(dp[i], ans)
    }
    return ans;
};
Copy the code

The time complexity of the above method is O(n2). The time complexity of the above method is O(nlogn). The time complexity of the above method is O(nlogn).

Feel helpful to you trouble dot a praise to walk ~

The code of this article has been included in Github, the warehouse includes the previous article links and code included, the subsequent code will be updated, welcome your comments.