精华内容
下载资源
问答
  • 动态规划算法的四个基本步骤
    千次阅读
    2020-10-05 16:19:51

    第一步,确定问题状态

    动态规划问题求解需要先开一个数组,并确定数组的每个元素f[i]代表什么,就是确定这个问题的状态。
    类似于解数学题中,设定X,Y,Z代表什么。

    a.确定状态首先提取

    最优策略必定是K枚硬币a1, a2,…, aK 面值加起来是27。
    找出不影响最优策略的最后一个独立角色,这道问题中,那枚最后的硬币“aK”就是最后一步。
    把aK提取出来,硬币aK之前的所有硬币面值加总是27- aK
    因为总体求最硬币数量最小策略,所以拼出27- aK 的硬币数也一定最少

    转化子问题

    如果aK是2,f(27)应该是f(27-2) + 1 (加上最后这一枚面值2的硬币)
    如果aK是5,f(27)应该是f(27-5) + 1 (加上最后这一枚面值5的硬币)
    如果aK是7,f(27)应该是f(27-7) + 1 (加上最后这一枚面值7的硬币)
    至此,通过找到原问题最后一步,并将其转化为子问题。
    为求面值总额27的最小的硬币组合数的状态就形成了,用以下函数表示:

    f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}

    第二步,转移方程,把问题方程化。

    f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
    (动态规划都是要开数组,所以这里改用方括号表示)

    第三步,按照实际逻辑设置边界情况和初始条件。

    必做】否则即使转移方程正确也大概率无法跑通代码。
    也就是确立问题初始值,这是动态规划无法推测的

    第四步,确定计算顺序并计算求解

     public int coinChange(int[] coins, int amount) {
                if (amount==0) return 0;
                if (amount < 0) return -1;
               /** 比如你想求 amount = 11 时的最少硬币数(原问题),
                如果你知道凑出 amount = 10 的最少硬币数(子问题),
                你只需要把子问题的答案加一(再选一枚面值为 1 的硬币)就是原问题的答案。
                因为硬币的数量是没有限制的,所以子问题之间没有相互制,是互相独立的。*/
               int[] dp=new int[amount+1];
               Arrays.fill(dp,amount+1);
               dp[0]=0;
                for (int i = 0; i <dp.length; i++) {
                    for(int coin:coins){
                      if (i-coin<0) continue;
                        dp[i]=Math.min(dp[i],1+dp[i-coin]);
                    }
                }
                //如果最后两个不相等,表示无法使用里面的硬币兑换
            return (dp[amount] == amount + 1) ? -1 : dp[amount];
            }
    
    更多相关内容
  • //第一步确定状态:假设就是想要求得最后的amount是11,则要算得最后一枚硬币面值为j,则(11-j); //第二步转移方程:假设i是要凑成的金额;则f[i]=min{f[i-1]+1,f[i-2]+1,f[i-3]...//第部计算顺序f[1].....f[a...

    //第一步确定状态:假设就是想要求得最后的amount是11,则要算得最后一枚硬币面值为j,则(11-j);
    
    //第二步 转移方程:假设i 是要凑成的金额;则f[i] = min{f[i - 1]+1,f[i - 2] + 1, f[i-3]+1} 这里算得的是amount;
    
    //第三部初始化条件和边界情况:1、首先如果f[i - 1]小于0,则都返回正无穷,f[0] = 0(算不出来的才要初始化) ; 边界情况a[j] <= i才可以进行计算
    
    //第四部 计算顺序f[1].....f[amount];
    
    // //这里注意,我们把 dp 数组初始化为 amount + 2 而不是-1 的原因是,在动态规划过程中有求
    
    // 最小值的操作,如果初始化成-1 则会导致结果始终为-1。至于为什么取这个值,是因为 i 最大可
    
    // 以取 amount + 1,而最多的组成方式是只用 1 元硬币,因此 amount + 2 一定大于所有可能的组合
    
    // 方式,取最小值时一定不会是它。在动态规划完成后,若结果仍然是此值,则说明不存在满足条
    
    // 件的组合方法,返回-1
    
    class Solution {
    
    public:
    
        int coinChange(vector<int>& coins, int amount) {
    
            //首先需要一个数组来放计算出来的值,并初始化为amount + 2(或者其他不影响计算的值例如:正无穷)
    
            int max = amount + 2;
    
            vector<int> dp (amount + 1, max);
    
            dp[0] = 0;
    
            for(int i = 1;i <= amount;i++ )
    
                for(int j = 0;j<coins.size();j++)
    
                {
    
                    //第二步 转移方程:假设i 是要凑成的金额;则f[i] = min{f[i - 1]+1,f[i - 2] + 1, f[i-3]+1} 这里算得的是amount;
    
                    if(coins[j] <= i)
    
                        dp[i] = min(dp[i - coins[j]] + 1,dp[i]);
    
                }
    
                
    
            return dp[amount] > amount ? -1 : dp[amount];
    
        }
    
    };
    
    
    
    

     

    展开全文
  • 图解动态规划的解题四步骤

    千次阅读 2020-04-02 20:36:44
    本文会以 House Robber 题目为例子,讲解动态规划题目的四个基本步骤动态规划的的四个解题步骤是: 定义子问题 写出子问题的递推关系 确定 DP 数组的计算顺序 空间优化(可选) 下面我们一步一步地进行讲解。 ...

    如果你对于动态规划还不是很了解,或者没怎么做过动态规划的题目的话,那么 House Robber (小偷问题)这道题是一个非常好的入门题目。本文会以 House Robber 题目为例子,讲解动态规划题目的四个基本步骤。

    动态规划的的四个解题步骤是:

    • 定义子问题
    • 写出子问题的递推关系
    • 确定 DP 数组的计算顺序
    • 空间优化(可选)

    下面我们一步一步地进行讲解。

    步骤一:定义子问题

    稍微接触过一点动态规划的朋友都知道动态规划有一个“子问题”的定义。什么是子问题?子问题是和原问题相似,但规模较小的问题。例如这道小偷问题,原问题是“从全部房子中能偷到的最大金额”,将问题的规模缩小,子问题就是“从 k 个房子中能偷到的最大金额”,用 f(k) 表示。

    在这里插入图片描述

    可以看到,子问题是参数化的,我们定义的子问题中有参数 kk。假设一共有 nn 个房子的话,就一共有 nn 个子问题。动态规划实际上就是通过求这一堆子问题的解,来求出原问题的解。这要求子问题需要具备两个性质:

    • 原问题要能由子问题表示。例如这道小偷问题中,k=nk=n 时实际上就是原问题。否则,解了半天子问题还是解不出原问题,那子问题岂不是白解了。
    • 一个子问题的解要能通过其他子问题的解求出。例如这道小偷问题中,f(k)f(k) 可以由 f(k-1)f(k−1) 和 f(k-2)f(k−2) 求出,具体原理后面会解释。这个性质就是教科书中所说的“最优子结构”。如果定义不出这样的子问题,那么这道题实际上没法用动态规划解。

    小偷问题由于比较简单,定义子问题实际上是很直观的。一些比较难的动态规划题目可能需要一些定义子问题的技巧。

    步骤二:写出子问题的递推关系

    这一步是求解动态规划问题最关键的一步。然而,这一步也是最无法在代码中体现出来的一步。在做题的时候,最好把这一步的思路用注释的形式写下来。做动态规划题目不要求快,而要确保无误。否则,写代码五分钟,找 bug 半小时,岂不美哉?

    我们来分析一下这道小偷问题的递推关系:

    假设一共有 nn 个房子,每个房子的金额分别是 H0, H1, …,Hn-1,子问题 f(k)f(k) 表示从前 k 个房子(即 H0, H1,…Hk-1,中能偷到的最大金额。那么,偷 k 个房子有两种偷法:

    在这里插入图片描述

    k 个房子中最后一个房子是 Hk-1。如果不偷这个房子,那么问题就变成在前 k-1个房子中偷到最大的金额,也就是子问题 f(k-1)。如果偷这个房子,那么前一个房子 Hk-2显然不能偷,其他房子不受影响。那么问题就变成在前 k-2 个房子中偷到的最大的金额。两种情况中,选择金额较大的一种结果。

    f(k) = max{f(k-1), Hk-1 + f(k-2)}

    在写递推关系的时候,要注意写上 k=0k=0 和 k=1k=1 的基本情况:

    • 当 k=0 时,没有房子,所以 f(0) =0。
    • 当 k=1 时,只有一个房子,偷这个房子即可,所以 f(1) = H0

    这样才能构成完整的递推关系,后面写代码也不容易在边界条件上出错。

    步骤三:确定 DP 数组的计算顺序

    在确定了子问题的递推关系之后,下一步就是依次计算出这些子问题了。在很多教程中都会写,动态规划有两种计算顺序,一种是自顶向下的、使用备忘录的递归方法,一种是自底向上的、使用 dp 数组的循环方法。不过在 普通的动态规划题目中,99% 的情况我们都不需要用到备忘录方法,所以我们最好坚持用自底向上的 dp 数组。

    DP 数组也可以叫”子问题数组”,因为 DP 数组中的每一个元素都对应一个子问题。如下图所示,dp[k] 对应子问题 f(k),即偷前 kk 间房子的最大金额。

    在这里插入图片描述

    那么,只要搞清楚了子问题的计算顺序,就可以确定 DP 数组的计算顺序。对于小偷问题,我们分析子问题的依赖关系,发现每个 f(k) 依赖 f(k-1) 和 f(k−2)。也就是说,dp[k] 依赖 dp[k-1] 和 dp[k-2],如下图所示。

    在这里插入图片描述

    那么,既然 DP 数组中的依赖关系都是向右指的,DP 数组的计算顺序就是从左向右。这样我们可以保证,计算一个子问题的时候,它所依赖的那些子问题已经计算出来了。

    确定了 DP 数组的计算顺序之后,我们就可以写出题解代码了:

    Java:

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // 子问题:
        // f(k) = 偷 [0..k) 房间中的最大金额
    
        // f(0) = 0
        // f(1) = nums[0]
        // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
    
        int N = nums.length;
        int[] dp = new int[N+1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int k = 2; k <= N; k++) {
            dp[k] = Math.max(dp[k-1], nums[k-1] + dp[k-2]);
        }
        return dp[N];
    }
    

    步骤四:空间优化

    空间优化是动态规划问题的进阶内容了。对于初学者来说,可以不掌握这部分内容。

    空间优化的基本原理是,很多时候我们并不需要始终持有全部的 DP 数组。对于小偷问题,我们发现,最后一步计算 f(n) 的时候,实际上只用到了 f(n-1) 和 f(n-2) 的结果。n-3 之前的子问题,实际上早就已经用不到了。那么,我们可以只用两个变量保存两个子问题的结果,就可以依次计算出所有的子问题。下面的动图比较了空间优化前和优化后的对比关系:

    在这里插入图片描述

    这样一来,空间复杂度也从 O(n)O(n) 降到了 O(1)O(1)。优化后的代码如下所示:

    Java:

    public int rob(int[] nums) {
        int prev = 0;
        int curr = 0;
    
        // 每次循环,计算“偷到当前房子为止的最大金额”
        for (int i : nums) {
            // 循环开始时,curr 表示 dp[k-1],prev 表示 dp[k-2]
            // dp[k] = max{ dp[k-1], dp[k-2] + i }
            int temp = Math.max(curr, prev + i);
            prev = curr;
            curr = temp;
            // 循环结束时,curr 表示 dp[k],prev 表示 dp[k-1]
        }
    
        return curr;
    }
    

    题目 打家劫舍

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

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

    示例

    示例 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 。

    展开全文
  • 动态规划4步骤

    千次阅读 2021-06-24 10:37:26
    动态规划时候通常需要开一数组,数组的每元素f[i]或者f[i][j]代表什么 类似于解数学题中,x,y, z代表什么 确定状态需要两意识 – 最后一步(最优策略中使用的最后一枚硬币ak) – 化成子问题(最少的硬币拼...

    动态规划可解决问题类型:

    1.计数

    • 有多少种方式走到右下角
    • 有多少种方法选出k个数使得和是sum
      2.求最大最小值
    • 从左上角走到右下角路径的最大数字和
    • 最长上升子序列长度
      3.存在性
    • 取石子游戏,先手是否必胜
    • 能不能选出k个数使得和是sum

    动态规划4个组成部分:

    1.确定状态

    • 解动态规划时候通常需要开一个数组,数组的每个元素f[i]或者f[i][j]代表什么
    • 类似于解数学题中,x,y, z代表什么
    • 确定状态需要两个意识
      – 最后一步(最优策略中使用的最后一枚硬币ak)
      – 化成子问题(最少的硬币拼出更小的面值27-ak)

    2.转移方程

    • 设状态f[x]=最少用多少枚硬币拼出x
    • 对于任意x,f[x] = min{f[x-2]+1 , f[x-5]+1, f[x-7]+1}

    3.初始条件和边界情况

    • f[x] =min{f[x-2]+1, f[x-5]+1, f[x-7]+1}
    • 两个问题:x-2, x-5或者x-7小于0怎么办?什么时候停下来?
    • 初始条件:f[0]=0
    • 如果不能拼出Y,就定义f[Y]=正无穷
      – 如f[-1] = f[-2] = … =正无穷
    • 所以f[1]=min{f[-1]+1, f[-4]+1, f[-6]+1} = 正无穷,表示拼不出来1

    4.计算顺序

    • 大多数动态规划问题一维计算都是从小到大,二维都是从左到右,从上到下计算,但也有一些动态规划问题计算顺序正好相反
    • 判断原则:当我们需要计算右边状态时,上一个左边的状态是否已经计算完了

    递归算法的特点:

    • 消除冗余,加速计算
    • 与递归算法相比,没有任何重复计算

    例:
    有5种物品A,B,C,D,E,对应重量为{2,2,6,5,4},对应价值为{6,3,5,4,6},背包总容量为10,计算背包能装下的最大价值?

    • 确定状态:
      – 最后一步:最后选择的一个物品i
      – 化成子问题:不超过重量10能得到的最大价值V(10-weights[i])
    • 转移方程:
      – 下一个阶段k:Value = max(V(i), V(10-weights[i]) + V(i+1))
      – 初始条件:f[0]=0
    • 计算顺序:从上到下

    代码块:

    # 动态规划-背包问题
    import numpy as np
    
    count =5
    weight = 10
    values = [6,3,5,4,6]
    weights = [2,2,6,5,4]
    
    def dp(weight, count, weights, values):
        preline, curline = [0]*(weight + 1), [0]*(weight + 1)
    
        for i in range(count):
            #print(i)
            for j in range(weight + 1):
                #print(j)
                if weights[i] <= j:
                    curline[j] = max(preline[j], preline[j - weights[i]] + values[i])
            preline = curline[:]
        return curline[weight]
    
    print(dp(weight, count, weights, values))
    

    results:
    在这里插入图片描述

    展开全文
  • 详解动态规划算法(Python)

    千次阅读 2020-11-08 20:32:21
    动态规划解题组成部分 1、确定状态 解动态规划的时候需要一数组,数组的每元素F[i],或者F[i,j]代表什么需要明确; 确定状态需要两意识: 1.1 最后一步 k枚硬币a a a...a,面值加起来应该等于11,最后的...
  • 详解动态规划算法

    千次阅读 多人点赞 2020-04-09 07:59:47
    给定不同面额的硬币 coins 和一总金额 amount。编写一函数来计算可以凑成总金额所需的最少的硬币数。如果没有任何一种硬币组合能组成总金额,返回 -1。输入: coins = [1, 2, 5], amount = 11,输出: 3 解释: ...
  • 动态规划算法

    千次阅读 2018-10-17 22:25:52
    相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间,查找了相关的文献和资料准备彻底的理解动态规划(Dynamic Programming)算法。一是帮助自己总结...
  • 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 什么是动态规划 动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题...
  • 陈甜甜【摘要】介绍了动态规划基本理论,包括动态规划基本概念和基本原理,并针对生产与存储问题进行了分析,然后结合Matlab做了编程处理,使复杂问题简单化,从而使问题能更方便地得到解决。【关键词】动态规划...
  • 矩阵连乘——动态规划算法

    千次阅读 多人点赞 2019-07-25 11:26:21
    矩阵连乘——动态规划算法 目录 矩阵连乘——动态规划算法 预备知识 前言 问题 应用动态规划方法的步骤 按照步骤分析问题 步骤1:最有括号化方案的结构特征 步骤2:一递归求解方案 步骤3:计算最优代价 ...
  • 算法-动态规划算法(详解)

    万次阅读 多人点赞 2020-10-10 20:46:22
    2)动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 3)与分治法不同的是,适合于用动态规划求解的问题,经分解得到的子问题往往...
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...
  • 这里写目录标题1 贪心算法1.1 介绍1.2 案例(最短路径)2 分治算法2.1 介绍2.2 基本思想2.3 解题步骤2.4 应用场景2.5 分治与递归的联系2.6 案例(海量数据处理)2.6.1 题目要求2.6.2 解题思路3 回溯算法3.1 介绍3.2 ...
  • 目录:算法分析与设计实验报告——0-1背包问题的动态规划算法实现一、 实验目的二、实验要求三、 实验原理、 实验过程(步骤)五、 运行结果六、实验分析与讨论七、实验特色与心得附件一 实验过程(步骤)附件二 运行...
  • 动态规划算法(详细解析)

    千次阅读 2020-04-29 16:45:58
    转载:https://blog.csdn.net/qq_37763204/article/details/79394397?utm_source=distribute.pc_relevant.none-task-blog-baidujs-5 一、基本概念    动态规划是运筹学中用于求解决...
  • 蓝桥杯必备算法三:动态规划

    千次阅读 多人点赞 2022-03-21 22:10:02
    动态规划算法原理1.0 算法引入2.0 什么问题能通过动态规划解决?3.0 解题步骤经典例题老鹰吃小鸡题目描述题目思路及代码删括号题目描述题目思路及代码结语 算法原理 1.0 算法引入 动态规划相信大家都知道,动态规划...
  • Java数据结构和算法——动态规划做题步骤详细总结

    千次阅读 多人点赞 2020-07-11 18:19:48
    文章目录动态规划题目类型动态规划解题步骤动态规划实例讲解硬币问题机器人路径问题青蛙跳石头问题 动态规划题目类型 1、计数: 有多少种方式走到右下角 有多少种方法选出k数使得和为Sum 2、求最大最小值: 从左上...
  • 动态规划及贪心算法

    千次阅读 2020-02-22 08:39:47
    大家可能在公司里面都有一定的组织架构,可能有高级经理、经理、总监、组长然后才是小开发,今天我们通过这例子,来讲讲什么问题适合使用动态规划。又到了一年一度的考核季,公司要挑选出三最优秀的员工。一...
  • 动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章,大多都是...
  • 我们在面对很多问题时,会通过递归去解决问题,虽然递归的代码写起来...而我们本文要讲的动态规划的思想正好和递归的思想相反,其主要思想是先从一个个小问题开始解决,直到所有小问题都解决了,整个问题就得以解答。
  • 动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答案,但就是自己不会做,不知道怎么下手。就像做...
  • 基于01背包问题的动态规划算法

    千次阅读 2020-08-12 00:31:59
    并且提到了动态规划算法基本思想与分治法类似,都是把原问题分解成子问题进行求解。而不同之处,也是动态规划的核心之处,在于动态规划自底向上地求出子问题中的局部最优解并记录下来,从而推导出全局最优解(即原...
  • 利用动态规划算法实现0-1背包问题 要求:测试数据以文本文件的形式存储,即所有的数据由文本文件读入。 package Zero_one_Package; import java.io.BufferedReader; import java.io.FileReader; import java....
  • 基础阶段()——MDP的动态规划算法 前言 一、pandas是什么? 二、使用步骤 1.引入库 2.读入数据 总结 前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门...
  • 1.加深对动态规划算法基本原理的理解,掌握用动态规划方法求解最优化问题的方法步骤及应用; 2.用动态规划设计整数序列的最长递增子序列问题的算法,分析其复杂性,并实现; 3.用动态规划设计求凸多边形的三角剖分...
  • 0-1背包问题的动态规划算法实现 一、实验目的和要求: 1.掌握动态规划算法思想。 2.掌握最优子结构原理。 3.了解动态规划一般问题,并利用动态规划解决0-1背包问题。 二、实验环境: VS2019 – .cpp文件 三、...
  • 五大常用算法之二:动态规划算法

    万次阅读 2018-03-14 12:52:53
    动态规划算法一、基本概念 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。二、基本思想与...
  • 在学习动态规划之前,我们必须要先掌握记忆化搜索和递推,这两块东西搞好了之后,面对动态规划那就容易多啦!好,接下来向铁汁们详细介绍这两块内容,走着。 一、记忆化搜索 提问: 何为记忆化搜索? 回答:...
  • 例子是求解矩阵链相乘问题的动态规划算法。给定一n矩阵的序列(矩阵链)(A1.A2.⋯ ,An)(A_1. A_2. \cdots, A_n)(A1​.A2​.⋯,An​),我们希望计算它们的乘积A1A2⋯AnA_1A_2\cdots A_nA1​A2​⋯An​其中,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,687
精华内容 15,474
热门标签
关键字:

动态规划算法的四个基本步骤

友情链接: Hafta 14.rar