【js】-【动态规划】-笔记

1 如何优雅地找硬币

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例1：
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例2：
输入: coins = [2], amount = 3
输出: -1

const coinChange = function(coins, amount) {
    
    # 用于保存每个目标总额对应的最小硬币个数
    const f = []

    f[0] = 0
    
    # 遍历 [1, amount] 这个区间的硬币总额
    for(let i=1;i<=amount;i++) {
    
        # 求的是最小值，我们预设为无穷大
        f[i] = Infinity
        // 循环遍历每个可用硬币的面额
        for(let j=0;j<coins.length;j++) {
    
            # 若硬币面额小于目标总额，则问题成立
            if(i-coins[j]>=0) {
    
                // 状态转移方程
                f[i] = Math.min(f[i],f[i-coins[j]]+1)
            }
        }
    }
    // 若目标总额对应的解为无穷大，则意味着没有一个符合条件的硬币总数来更新它，本题无解，返回-1
    if(f[amount]===Infinity) {
    
        return -1
    }
    // 若有解，直接返回解的内容
    return f[amount]
};

2 0-1背包问题

有 n 件物品，物品体积用一个名为 w 的数组存起来，物品的价值用一个名为 value 的数组存起来；每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？
注意：每种物品都只有1件

# 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
function knapsack(n, c, w, value) {
    
    // dp是动态规划的状态保存数组
    const dp = (new Array(c+1)).fill(0)  
    
    # res 用来记录所有组合方案中的最大值
    let res = -Infinity
    for(let i=1;i<=n;i++) {
    
        for(let v=c;v>=w[i];v--) {
    
            // 写出状态转移方程
            dp[v] = Math.max(dp[v], dp[v-w[i]] + value[i])
            // 即时更新最大值
            if(dp[v] > res) {
    
                res = dp[v]
            }
        }
    }
    return res
}

3 最长上升子序列模型

题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

var lengthOfLIS = function(nums) {
    
    if(!nums.length) return 0;
    # 初始化数组里面每一个索引位的状态值
    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(nums[j]<nums[i]) dp[i]=Math.max(dp[i],dp[j]+1);
        }
        res= Math.max(dp[i],res);
    }
    return res;
};