[JS] - [dynamic planning] - Notes

1 How to find coins gracefully

Give coins of different denominations coins And a total amount amount. Write a function to calculate the amount needed to make up the total amount least Number of coins . If no combination of coins can make up the total amount , return -1.

 Example 1：
 Input : coins = [1, 2, 5], amount = 11
 Output : 3
 explain : 11 = 5 + 5 + 1

 Example 2：
 Input : coins = [2], amount = 3
 Output : -1

const coinChange = function(coins, amount) {
    
    #  It is used to save the minimum number of coins corresponding to each target total 
    const f = []

    f[0] = 0
    
    #  Traverse  [1, amount]  The total amount of coins in this range 
    for(let i=1;i<=amount;i++) {
    
        #  It's the minimum , We assume infinity 
        f[i] = Infinity
        //  Loop through the denomination of each available coin 
        for(let j=0;j<coins.length;j++) {
    
            #  If the denomination is less than the target total , Then the problem holds 
            if(i-coins[j]>=0) {
    
                //  State transition equation 
                f[i] = Math.min(f[i],f[i-coins[j]]+1)
            }
        }
    }
    //  If the solution corresponding to the target sum is infinite , It means that there is no eligible total number of coins to update it , There is no solution to this problem , return -1
    if(f[amount]===Infinity) {
    
        return -1
    }
    //  If there is a solution , Return the content of the solution directly 
    return f[amount]
};

2 0-1 knapsack problem

Yes n Item , The volume of the object is called w Save the array of , The value of an item is called value Save the array of ; The volume of each article is w[i] To express , The value of each item is value[i] To express . There is now a capacity of c The backpack , Ask how you choose items to put into your backpack , In order to maximize the total value of the items in the backpack ？
Be careful ： There are only 1 Pieces of

#  Participation is the number of items and the upper limit of the backpack , And an array of weights and values of items 
function knapsack(n, c, w, value) {
    
    // dp Is a dynamic planning state saving array 
    const dp = (new Array(c+1)).fill(0)  
    
    # res  It is used to record the maximum value in all combination schemes 
    let res = -Infinity
    for(let i=1;i<=n;i++) {
    
        for(let v=c;v>=w[i];v--) {
    
            //  Write the equation of state transition 
            dp[v] = Math.max(dp[v], dp[v-w[i]] + value[i])
            //  Update the maximum value immediately 
            if(dp[v] > res) {
    
                res = dp[v]
            }
        }
    }
    return res
}

3 Longest ascending subsequence model

Title Description ： Given an unordered array of integers , Find the length of the longest ascending subsequence .

 Example :
 Input : [10,9,2,5,3,7,101,18]
 Output : 4
 explain :  The longest ascending subsequence is  [2,3,7,101], Its length is  4.

var lengthOfLIS = function(nums) {
    
    if(!nums.length) return 0;
    #  Initialize the status value of each index bit in the array 
    const dp= new Array(nums.length).fill(1);

    let res =1;
    for(let i=1;i<nums.length;i++){
    
        for(let j=0;j<i;j++){
    
       #  If you encounter a value smaller than the current element , It means that an ascending subsequence that can be extended , Therefore, update the status corresponding to the index bit of the current element 
            if(nums[j]<nums[i]) dp[i]=Math.max(dp[i],dp[j]+1);
        }
        res= Math.max(dp[i],res);
    }
    return res;
};