这些力扣题目来源：AI推荐+karshey博主

目录

70 爬楼梯（通过）

746 最小代价（通过）

198 打家劫舍（通过）

（二错题）53 最大子数组和（超高频）（通过）

62 不同路径（二维 DP 入门）（通过）

416 分割等和子集（0-1 背包入门）（通过）

322 零钱兑换（完全背包入门）（通过）

---

70 爬楼梯（通过）

70 爬楼梯

最重要的是状态转换方程：一共有两种方法到达现在的位置：从n-1层走1层，或者从n-2层走两层到达目的地。

使用递归会超时

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {

    let plan = Array(46).fill(0);
    plan[1]=1;
    plan[2]=2;
    for(let i=3;i<=n;i++){
        plan[i]=plan[i-1]+plan[i-2];
    }
    return plan[n];
    //递归法超时 通过用例21/45
    // if (n==1) return 1;
    // if (n==2) return 2;
    // return climbStairs(n-1)+climbStairs(n-2); 
};

746 最小代价（通过）

746 最小代价

爬楼梯变种：只有两种方法到达目标层数，要么通过踏一步的方式，要么通过踏两步的方式。

到达每一层的最小代价的状态方程为：lowestCost[i]=Math.min(cost[i-2]+lowestCost[i-2],cost[i-1]+lowestCost[i-1]);

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    let lowestCost = Array(1001).fill(0);
    for(let i=2;i<=cost.length;i++){
        lowestCost[i]=Math.min(cost[i-2]+lowestCost[i-2],cost[i-1]+lowestCost[i-1]);
    }
    return lowestCost[cost.length]
};

198 打家劫舍（通过）

198 打家劫舍

爬楼梯变种：只有两种方式到达最后一家：要么跳过一家，要么跳过走两家。不可能连续跳过三家，这样会拉下钱，因为每家现金不为负。

注意第I家的最大积累金额未必是以I为界限的打劫（money[i-2]+nums[i]），有可能是以I-1为界限(mone[i-1])的打劫。比较大小确定哪一个是以N家为界限的最大打劫金额

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    let money = Array(101).fill(0);
    money[0] = nums[0];
    if(nums.length<=1) return money[0];

    money[1] = Math.max(nums[0],nums[1]);
    for(let i=2;i<nums.length;i++){
        money[i]=Math.max( money[i-2]+nums[i],money[i-1]);
    }
    return money[nums.length-1];
};

（二错题）53 最大子数组和（超高频）（通过）

53 最大子数组和（超高频）

第一次只能想出来暴力解法：超时，只能解出来203/210个用例。

看了Deepseek的答案，使用了 Kadane（O(n)）算法

包含第i+1个数字的最大子数组，只有两种可能：dp[i]+nums[i]（前面和为正数），nums[i]（前面和为负数或零，可以舍弃）

用一个max=-infinity记录每一轮的最大数组得出所有子数组的最大数组

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

nums = [-2,1,-3,4,-1,2,1,-5,4]

var maxSubArray = function(nums) {


    //  Kadane（O(n)）算法：要么前面和+当前数字，要么重新开始（前面和为负数或0）
    let dp = Array(nums.length+1).fill(0);
    let max = -Infinity;
    for(let i=0;i<nums.length;i++){
        dp[i+1] = Math.max(dp[i]+nums[i],nums[i]);
        max=dp[i+1]>max?dp[i+1]:max;
    }
    return max;

    //暴力法：超时 通过203/210个用例
    // let preSum_arr = [];
    // let preSum=0;
    // preSum_arr.push(0);
    // for(let i=0;i<nums.length;i++){
    //     preSum+=nums[i];
    //     preSum_arr.push(preSum);
    // }  


    // max = -Infinity;
    // for(let i=1;i<preSum_arr.length;i++){
    //     for(let j=0;j<i;j++){
    //         max = preSum_arr[i]-preSum_arr[j]>max?preSum_arr[i]-preSum_arr[j]:max;
    //     }
    // }
    // return max;
};

console.log(maxSubArray(nums));

62 不同路径（二维 DP 入门）（通过）

62 不同路径（二维 DP 入门）

其实这道题有轮换对称性，从dp[m][n]走到dp[0][0]的方法个数等于从dp[0][0]走到dp[m][n]

初始化二维dp，初始值为1, dp[1][0] 是 dp[0][0]向上走一步得到的，dp[0][1]是dp[0][0]向左走一步得到的

状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]，因为每个格子只有两种方法可以走到那里

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let dp = Array(m).fill(0).map(()=>Array(n).fill(1));
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            dp[i][j] = dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
};

// console.log(uniquePaths(3,3))
console.log(uniquePaths(3,2))

416 分割等和子集（0-1 背包入门）（通过）

416 分割等和子集（0-1 背包入门）

不完全背包问题：（凑出数字等价于能装载重量）。每个元素只能用一次

如果值不是偶数，证明不能分割成两份子集

下面两个判断决定了能否凑出来数字 j 

第一种情况，给定数组中恰好包含。num[i]恰好等于j，可以凑出j这个数字

第二种情况，dp[j-num[i]]为true，代表j减去当前数字的数之前凑出来过，再加上当前数组数字，可以凑出j这个数字

/**
 * @param {number[]} nums
 * @return {boolean}
 */

nums = [1,5,11,5]

var canPartition = function(nums) {
    let sum = 0;
    for(let i=0;i<nums.length;i++){
        sum+=nums[i];
    }
    if (sum%2==1) return false; //如果值不是偶数，证明不能分割成两份子集
    nums.sort((a,b)=>a-b);
    let half = sum/2

    let dp = Array(half+1).fill(false);
    for(let i=0;i<nums.length;i++){
        for(let j=half;j>0;j--){
            if(nums[i]==j || dp[j-nums[i]] ) dp[j]=true; 
            //第一种情况，num[i]恰好等于j，可以凑出j这个数字
            //第二种情况，dp[j-num[i]]为true，代表j减去当前数字的数之前凑出来过，可以凑出j这个数字
        }
    }
    return dp[half];
};

console.log(canPartition(nums));

322 零钱兑换（完全背包入门）（通过）

322 零钱兑换（完全背包入门）

完全背包问题，每个数字可以用无限次

边界条件：面额为零的时候，不需要任何货币 return 0;

货币面额需要升序，因为这样可以在后面用面值大的货币替换面值小的货币

两种情况：1.当前货币面值等于被凑货币 2.以前凑出来过的货币=目前需要凑的货币-当面货币面额

以前凑出来过，比较两者哪个用的货币少

核心：if(coins[i]==j || dp[j-coins[i]]!=Infinity ) dp[j] = coins[i]==j ?1 : Math.min(dp[j-coins[i]]+1,dp[j]) //以前凑出来过，比较两者哪个用的货币少

找不到的时候，返回-1

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
// coins = [1, 2, 5], amount = 11

//通过了99/189个用例
coins = [186,419,83,408], amount = 6249

var coinChange = function(coins, amount) {

    //边界条件
    if (amount == 0) return 0;

    let dp = Array(amount+1).fill(Infinity);

    //需要升序，因为这样可以在后面用面值大的货币替换面值小的货币
    coins.sort((a,b)=>a-b) 
    for(let i=0;i<coins.length;i++){
        for(let j=coins[i];j<dp.length;j++){
            //两种情况：1.当前货币面值等于被凑货币 2.以前凑出来过的货币=目前需要凑的货币-当面货币面额
            if(coins[i]==j || dp[j-coins[i]]!=Infinity ) dp[j] = coins[i]==j ?1 : Math.min(dp[j-coins[i]]+1,dp[j]) //以前凑出来过，比较两者哪个用的货币少 
        }
    }
    //三元运算符表示找不到的情况，返回-1
    return dp[amount]==Infinity?-1:dp[amount];
};

console.log(coinChange(coins, amount));