首页 > 其他分享 >动态规划

动态规划

时间:2023-02-05 10:25:45浏览次数:53  
标签:偷窃 nums 示例 金额 amount 房屋 动态 规划

动态规划

  • 算法设计的一种思想
  • 将问题分解为相互重叠的子问题,对子问题进行求解,从而解决原问题

1. 动态规划和分治

  • 区别
    • 分治的子问题,相互独立,互不干扰
    • 动态规划的子问题相互重叠
      • 如斐波那契求和:f(n)=f(n-1)+f(n-2):f(n-1) 和f(n-2) 之间是不是存在联系(f(n-1)=f(n-2)+f(n-3))

LeetCode

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示:

  • 1 <= n <= 45
1. 看问题的类型,明显不是让你求出一个确定的值,也不是对原数据进行改造
2. 求最大的爬楼梯方法,递归
3. 转换为小问题,爬n阶,==>爬n-1阶,n-2阶
4. 递归出口 n=1 1,n=2 2
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {

    // i*1+j*2=n  i和j在来一个全排列 i个位置填1 j个位置填2

    // const jMax=n/2;
    // for(let j=0;j<jMax;j++){
    //     const iCurr=n-2*jMax

    //     // 知道了当前j和i的个数
    // }

    // 爬上n阶楼梯
    // 两种情况,爬上(n-1)阶+1阶
    // 爬上(n-2)阶+2阶

    // 则爬上n阶楼梯的方法数为
    // 爬上n-1阶的方法数+n-2阶的方法数


    // 前缀和
    if(n<2){
        return 1
    }

    const dp=[1,1];

    for(let i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]
    }

    return dp[n]


};

198. 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
1. 能偷的最大金额,很明显这个最大值需要经过枚举才可以看出(肉眼不能看出),明显的划归
2. 偷n阶房屋,==> 偷n-1房屋(VS)偷n-2房屋+当前房屋
3. 递归出口 n=1 nums[0] 金额

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {

    // n阶房屋

    // 能偷的最大金额,n-2阶房屋的最大金额+当前房屋(n)的金额
    // 或者 n-1 阶房屋的最大金额

    // 递归出口 n=0 0,n=1 nums[0], n=2 max(nums[0],nums[1])

    if(!nums.length){
        return 0
    }
    if(nums.length===1){
        return nums[0]
    }

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

    return dp[nums.length]

};
  • 注意点
1. 这里面空间复杂度还可以优化
2. 没必要存储一个dp数组,我们要的是顶部元素

213. 打家劫舍 II

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3:

输入:nums = [1,2,3]
输出:3

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
1. 和第一版的打家劫舍相同,只是不能同时偷第一家和最后一家
2. 那我们把这个问题分解为偷0-(n-1)家
3. 和偷1-n家 
4. 看那个能偷盗最多的金额
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
        // n阶房屋

    // 能偷的最大金额,n-2阶房屋的最大金额+当前房屋(n)的金额
    // 或者 n-1 阶房屋的最大金额

    // 递归出口 n=0 0,n=1 nums[0], n=2 max(nums[0],nums[1])

    if(!nums.length){
        return 0
    }
    if(nums.length===1){
        return nums[0]
    }

    if(nums.length===2){
        return Math.max(nums[0],nums[1])
    }
    

    // 比对偷0-(n-1)家的金额大
    // 还是 1-n家的金额大
    const nums1=nums.slice(0,nums.length-1)
    const nums2=nums.slice(1,nums.length)


    const dp1=[0,nums1[0]]
    for(let i=2;i<=nums1.length;i++){
        dp1[i]=Math.max(dp1[i-2]+nums1[i-1],dp1[i-1])
    }

    // 不偷第一家
    const dp2=[0,nums2[0]]
    for(let i=2;i<=nums2.length;i++){
        dp2[i]=Math.max(dp2[i-2]+nums2[i-1],dp2[i-1])
    }

    return Math.max(dp1[nums1.length],dp2[nums2.length])
};

322. 零钱兑换

难度中等2157收藏分享切换为英文接收动态反馈

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

示例 1:

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

示例 2:

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

示例 3:

输入:coins = [1], amount = 0
输出:0

提示:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104
完整代码
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {

    // 使用类似爬楼梯的算法

    // 爬到n层
    // 需要最小的步数
    // 即(n-coins[i])+coins[i] 步

    // (n-coins[i]) 除了当前的硬币面额,已经爬了n-coins层的最小硬币数

    // 关键在于i是可以变化的,(爬楼梯就不仅仅是n-1阶或者n-2阶了)


    // 定义一个数组,存储爬到第k层的最小硬币数,默认设置最大值,因为面额1的话,就是amount,amount+1自然最大值
    let arr=new Array(amount+1).fill(amount+1)

    arr[0]=0

    // i 为爬的层数
    for(let i=0;i<=amount;i++){

        // coin为一次爬coin步(比对爬楼梯一次只能1或者2)
        for(let coin of coins){

            if(i-coin>=0){
                // 到了这里说明爬的层数大于等于(一次爬的),可以使用一次道具(一次爬coin步) 看步数是否减少
                arr[i]=Math.min(arr[i],arr[i-coin]+1)
            }
        }
    }

    return arr[amount]< amount+1? arr[amount]:-1
 
};

标签:偷窃,nums,示例,金额,amount,房屋,动态,规划
From: https://www.cnblogs.com/lingxin1123/p/17092935.html

相关文章

  • m基于自适应遗传优化的IEEE-6建设费用和网络损耗费用最小化电网规划算法matlab仿真
    1.算法描述电力工业是当今世界各国经济的重要组成部分,随着世界经济的不断发展,电网的建设和中长期规划和经济发展之间的矛盾变得越来越突出,对电力系统的需求也变得越来越大......
  • 基于遗传优化算法的小车障碍物避障路线规划matlab仿真
    1.算法描述一种通过模拟自然进化过程搜索最优解的方法,对于一个最优化问题,该算法通过一定数量的候选解种群迭代地执行选择、交叉、变异、评价等操作使得种群向更好的解进化......
  • 基于遗传优化算法的小车障碍物避障路线规划matlab仿真
    1.算法描述       一种通过模拟自然进化过程搜索最优解的方法,对于一个最优化问题,该算法通过一定数量的候选解种群迭代地执行选择、交叉、变异、评价等操作使得种群......
  • m基于自适应遗传优化的IEEE-6建设费用和网络损耗费用最小化电网规划算法matlab仿真
    1.算法描述        电力工业是当今世界各国经济的重要组成部分,随着世界经济的不断发展,电网的建设和中长期规划和经济发展之间的矛盾变得越来越突出,对电力系统的需......
  • 混合应用字符串插值、字符串格式方法生成动态查询语句
    Strings=String.Format("select*fromPrice_ItemDeptswhereFeeDeptID={0}{1}{2}",$"'{deptID}'",string.IsNullOrEmpty(categoryID)?""......
  • Java静态绑定和动态绑定
    将方法调用连接到方法体称为绑定。在java中有两种类型的绑定:静态绑定(也称为早期绑定)。动态绑定(也称为后期绑定)。了解类型下面让我们来了解实例的类型。1.变......
  • 动态代理-RPC实现核心原理
    实现过统一拦截吗?如授权认证、性能统计,可以用SpringAOP,不需要改动原有代码前提下,还能实现非业务逻辑跟业务逻辑的解耦。核心就是动态代理,通过对字节码进行增强,在方法调用......
  • 动态规划DP
    动态规划DP一般DP的组成一般DP主要分为两个部分:表示状态,状态转移这里以P1216[USACO1.5][IOI1994]数字三角形NumberTriangles为例表示状态答案为从上到下的路径......
  • 人生规划
    1,考研有用,但最好大学毕业就考,最多给自己两次机会。2,珍惜应届生身份,第一份工作不要随意签。一般来说公务员>人才引进>国企>外资>民企,但排序也可能随时代而变化。3,实在进不......
  • 2023网络爬虫 -- 获取动态加载数据
    1、爬取的网址http://www.kfc.com.cn/kfccda/storelist/index.aspx2、要爬取的内容,输入关键字,点击查询,获取餐厅名称和餐厅地址3、F12,打开开发者工具,点击查询,抓包4、点......