动态规划刷题合集

 

300. 最长递增子序列

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    let l=nums.length
    let dp=new Array(l).fill(1)
    for(let i=0;i<l;i++){
        for(let j=0;j<i;j++){
            if(nums[j]<nums[i])
            dp[i]=Math.max(dp[i] ,dp[j]+1)
        }
    }
    let maxn=0
    for(let i=0;i<l;i++){
        if(dp[i]>maxn){
            maxn=dp[i]
        }
    }
    return maxn

};

931. 下降路径最小和

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var minFallingPathSum = function(matrix) {
    //备忘录
    let m = matrix.length
    let n = matrix[0].length
 
    let memo = new Array(m).fill(0).map(item=>{
        return Array(n).fill(123456)
    })
    let res=9999999
    for(let j=0;j<n;j++){
        res = Math.min(dp(matrix,m-1,j),res)
    }
    return res
    




    function dp (matrix,i,j){
    // 1、索引合法性检查
    if(i<0 || j<0 ||
    i>=m ||
    j>=n)
    return 99999
    // 2、base case
    if(i==0)
    return matrix[0][j]
    // 3、查找备忘录，防止重复计算
    if(memo[i][j]!=123456)
    return memo[i][j]

    memo[i][j] = matrix[i][j] + Math.min(
        dp(matrix,i-1,j),
        dp(matrix,i-1,j-1),
        dp(matrix,i-1,j+1)
    )
    return memo[i][j]
}
};

322. 零钱兑换

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
      // 数组大小为 amount + 1，初始值也为 amount + 1
    let dp =new Array(amount+1).fill(amount+1)
    console.log(dp)
    dp[0]=0
    for(let i =0 ;i <=amount;i++){
      // 内层 for 在求所有子问题 + 1 的最小值
        for(let coin of coins){
            if(i-coin < 0) continue// 子问题无解，跳过
            dp[i] = Math.min(dp[i],dp[i-coin]+1)
        }
    }

    return (dp[amount] == (amount+1)) ? -1 : dp[amount]
};

53. 最大子数组和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let n=nums.length
    let dp=new Array(n).fill(0)
    for(let i=0;i<nums.length;i++){
        dp[i]=nums[i]
    }
    
    for(let i=1;i<nums.length;i++){
        
        dp[i]=Math.max(dp[i],dp[i-1]+nums[i])
        
    }
    let maxn=-949999
    for(let i=0;i<nums.length;i++){
        if(dp[i]>maxn)
        maxn=dp[i]
    }
    return maxn

};