精华内容
下载资源
问答
  • 关于动态规划之前刷过一些相关的题,但都是类似背包问题、爬楼梯问题,那时候觉得这个算法挺简单。直到最近看jieba的源码,其中两次使用到...觉得理解了一个问题为什么能够使用动态规划?拿到一个问题时,如何判...

    关于动态规划之前刷过一些相关的题,但都是类似背包问题、爬楼梯问题,那时候觉得这个算法挺简单。直到最近在看jieba的源码,其中两次使用到动态规划,一次是很有名的viterbi算法,另一次是在有向无环图中查找最优分词序列时。在看这两部分的源码时感觉自己对动态规划的理解太过浅薄,于是重新翻看《算法导论》的第15.3节----动态规划原理。觉得理解了一个问题为什么能够使用动态规划?拿到一个问题时,如何判断是否应该使用动态规划?对于书中的一些关键点做一些记录。

    最优子结构

    • 如果一个问题的最优解包含其子问题的最优解,我们就称此问题具有最优子结构
    • 一个问题具有最优子结构,可能使用动态规划方法,也可能使用贪心方法。所以最优子结构只是一个线索,不是看到有最优子结构就一定是用动态规划求解
    • 发掘最优子结构的通用模式:
    1. 证明问题最优解的第一个组成部分是做出一个选择,做出这次选择会产生一个或多个待解的子问题
    2. 对于一个给定问题,在其可能的第一步选择中,你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的,只是假定已经知道了这种选择
    3. 给定可获得最优解的选择后,你确定这次选择会产生哪些子问题,以及如何更好的刻画子问题空间
    4. 利用“剪切-粘贴”技术证明:作为构成原问题最优解的组成部分,每个子问题的解就是它本身的最优解。
    • 对于不同问题领域,最优子结构的不同体现在两个方面:
    1. 原问题的最优解中涉及多少个子问题
    2. 在确定最优解使用哪些子问题时,我们需要考察多少种选择
    • 动态规划与贪心的区别:
    1. 动态规划是先求解当前问题的所有子问题的最优解,然后在这些子问题中进行选择
    2. 贪心是首先做出一次“贪心”选择----在当时(局部)看来最优的选择----然后求解选出的子问题。所以贪心不需要求解所有的子问题
    • 当前问题的所有子问题应该是无关的,即一个子问题的解不会影响另一个子问题的求解。举例就是“无权最短路径问题”和“无权最长路径问题”,无权最短路径问题中子问题之间是无关的,而无权最长路径问题中各个子问题之间是相关的。无权最短路径问题可以用动态规划求解,而无权最长路径问题不可用动态规划求解。


    重叠子问题

    • 子问题空间必须足够“小”,即在不断的递归过程中,是在反复求解大量相同的子问题,而不是每次递归时都产生新的子问题。
    • 一般的,不同子问题的总数是输入规模的多项式函数为好
    • 如果递归算法反复求解相同的子问题,我们就称最优化问题具有重叠子问题性质
    • 动态规划与分治算法的区别:
    1. 适用动态规划求解的问题,在递归时是在求解大量相同的问题,这时可以将求解过的子问题缓存到一个数据结构中,当再次需要这个子问题时直接查缓存
    2. 适用分治法求解的问题,在递归时不断的产生新的子问题,比如快排,它必须每次求解该子问题的解
       

    真的是要不断学习,很多以为自己懂了,实际没有懂。

    展开全文
  • 动态规划在实际应用中十分广泛,经常在笔试中碰到动态规划的题目,而且理解起来也比较困难,灵活应用起来更加的不容易,今天就总结一下,到底在什么时候使用动态规划,以及怎么使用动态规划。 动态规划的使用场景...

    动态规划在实际应用中十分广泛,经常在笔试中碰到动态规划的题目,而且理解起来也比较困难,灵活应用起来更加的不容易,今天就总结一下,到底在什么时候使用动态规划,以及怎么使用动态规划。

    动态规划的使用场景一般包括三个特征:

       (1)最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构。

              比如要想求棋盘两对角的最短距离,那个每走一格算一格阶段,每一格最优解必定是在上一格的最优解中得来的,也就是说每一个阶段都有最优的一个决策代表最优子解。

       (2)无后效性:某一状态一旦确定,就不受这个状态的以后的决策影响。

               后效性是指,如果上面的例子中的每一个格子的长度是不一致的,那么在当前选择的格子决策背景下,可能会对后面选择决策造成影响,如下图。

                                        

                        如果选择了当前选择了值为10的这个节点,则会导致后续只能选择100,甚至200的节点,即在选择10和20节点的时候,会对后续的决策产生影响。

       (3)有重叠子问题:子问题之间不是相互独立的,一个子问题在下一阶段的决策中可能被多次使用到。

              即当前的最优解的计算,我们只需要记录下来,在后续的比较中使用到,而不需要再次计算,增加时间复杂度。

    动态规划的基本过程描述:

          每次决策依赖于当前状态,又引起状态的转移,一个决策序列就是在变化的状态中产生出来的,所以,动态规划可以看成是多阶段最优化决策来解决问题的过程。

    使用动态规划解决问题,最重要的就是确定动态的三要素:

       (1)问题的阶段。

       (2)每个阶段的状态。

       (3)从前一个阶段到后一个阶段的递推关系。

    下面我们看一个经典而简单的例子来阐述一下,动态规划到底怎么用来解决问题:

     1 package DP;
     2 
     3 /**
     4  * Created by jy on 2017/10/5.
     5  * 求解给定数组的子数组,使得子数组的和最大,子数组的元素在给定的数组中必须是连续的
     6  */
     7 public class MaxSumSubArray {
     8 
     9     /*dp解法:
    10     * 可以令curMax[]是以当前元素结尾的最大子数组和,maxSum是全局的最大子数组和,
    11     * 当往后扫描时,对第j个元素有两种选择:要么放入前面找到的子数组,要么做为新子数组的第一个元素
    12     * 举个例子,当输入数组是1, -2, 3, 10, -4, 7, 2, -5,那么,currSum和maxSum相应的变化为:
    13     *
    14     * j(前j个元素): 0    1     2    3     4    5     6     7     8
    15     * currSum[] :  0   1     -1    3    13    9    16    18    13
    16     * maxSum[]  :  0   1     1     3    13    13   16    18    18
    17     *
    18     *
    19     * 1.起始阶段(i=0),max = nums[0];
    20     * 2.第i(i > 0)个阶段,max = curMax[i],curMax是第i个阶段的最大子序列和;
    21     * 3.第i-1和第i个阶段的关系,curMax[i] = Math.max(curMax[i - 1] + nums[i], nums[i]);
    22     * 4.根据前面动态规划的定义,则最大子序列和max = Math.max(max, curMax[i])
    23     * */
    24     public static int DpMaxSubArray(int[] nums) {
    25         //curMax是当前的最大子序列和
    26         int[] curMax = new int[nums.length];
    27         //起始阶段
    28         curMax[0] = nums[0];
    29         //刻画最优解
    30         int max = nums[0];
    31         for (int i = 1; i < nums.length; i++) {
    32             //每一阶段的最优都有上一阶段的最优的基础上而来
    33             curMax[i] = Math.max(curMax[i - 1] + nums[i], nums[i]);
    34             System.out.print(curMax[i] + " ");
    35             max = Math.max(max, curMax[i]);
    36         }
    37         return max;
    38     }
    39 }

     通常动态规划都有一个阶段的概念,在这里的阶段就是前多少个元素,求前两个元素的最大子数组就是一个阶段,求前三个元素的最大子数组是一个阶段......每一个阶段的最优解都放在一个数组里记录,用于在下一阶段中比较,

    在这个问题中,如果第n-1 阶段的最大和比第n个元素还要小,则当前的第n个元素作为最优子结构(最大和子数组)的开头第一个元素,继续往后扫描,而最大和就在currMax[i]中产生。

       我们再来看看一个经典的0-1背包问题:

    求解背包问题:
    * 给定 n 个物品,其重量分别为 w1,w2,……,wn, 价值分别为 v1,v2,……,vn
    * 要放入总承重为 totalWeight 的箱子中,
    * 求可放入箱子的背包价值总和的最大值。
     1 class ZeroOneProblem {
     2 
     3     //定义背包为item集合,item有两个属性,一个是weight,一个是value
     4     private Item[] item;
     5 
     6     //总重量
     7     private int totalWeight;
     8 
     9     //物品数量
    10     private int n;
    11 
    12     //装n个物品,总重量为totalWeight的最优解
    13     private int[][] bestValues;
    14 
    15     //装n个物品,总重量为totalWeight的最优值
    16     private int bestValue;
    17 
    18     //装n个物品,总重量为totalWeight的最优时的物品组成
    19     private ArrayList<Item> bestSolution;
    20     
    21     // 求解前 n 个背包、给定总承重为 totalWeight 下的背包问题
    22     public void solve() {
    23         System.out.println("给定物品:");
    24         for (Item item : item) {
    25             System.out.println(item);
    26         }
    27         System.out.println("给定总承重: " + totalWeight);
    28         //i为0时,表示没有物品,j为0时表示没有重量
    29         for (int j = 0; j <= totalWeight; j++) {
    30             for (int i = 0; i <= n; i++) {
    31                 if (i == 0 || j == 0) {
    32                     bestValues[i][j] = 0;
    33                 } else {
    34                     // 如果第 i 个物品重量大于此时的剩下的承重,则最优解存在于前 i-1 个物品中,第i个物品不放进去
    35                     // 第 i 个物品是 item[i-1]
    36                     if (j < item[i - 1].getWeight()) {
    37                         bestValues[i][j] = bestValues[i - 1][j];
    38                     } else {
    39                         // 如果第 i 个物品不大于总承重,则最优解要么是包含第 i 个物品的最优解,
    40                         // 要么是不包含第 i 个物品的最优解, 取两者最大值。
    41                         // 第 i 个物品的重量 iweight 和价值 ivalue
    42                         int iweight = item[i - 1].getWeight();
    43                         int ivalue = item[i - 1].getValue();
    44                         bestValues[i][j] =
    45                                 Math.max(bestValues[i - 1][j], ivalue + bestValues[i - 1][j - iweight]);
    46                     }
    47                 }
    48             }
    49         }
    50 
    51         // 回溯:求解背包组成
    52         if (bestSolution == null) {
    53             bestSolution = new ArrayList<Item>();
    54         }
    55         int tempWeight = totalWeight;
    56         for (int i = n; i >= 1; i--) {
    57             if (bestValues[i][tempWeight] > bestValues[i - 1][tempWeight]) {
    58                 bestSolution.add(item[i - 1]);  // item[i-1] 表示第 i 个物品
    59                 tempWeight -= item[i - 1].getWeight();
    60             }
    61             if (tempWeight == 0) {
    62                 break;
    63             }
    64         }
    65         bestValue = bestValues[n][totalWeight];
    66     }

      如果还是理解不了具体是怎么做的,可以看下面的决策表的生成过程 ,物品如下:

    [weight: 2 value: 13]
    [weight: 1 value: 10]
    [weight: 3 value: 24]
    [weight: 2 value: 15]
    [weight: 4 value: 28]
    [weight: 5 value: 33]
    [weight: 3 value: 20]
    [weight: 1 value: 8]

    totalWeight = 5时,bestValues[6][9](只有蓝色部分)数组的产生过程:

    详解一下红色的34是怎么得到的:此时背包重量为4,只能选择前3个物品,且当前物品重量为3,小于背包的承重4,bestValues[3][4] = max{  bestValues[2][4]   ,  24+bestValues[2][1]  } , 比较的是不放编号3的物品时最大value和放编号3的物品时的最大value。

     

    关于动态规划就讲到这里啦,我觉得最难的地方在于怎么把问题分阶段的考虑,以及推导出递推式子。

    如有错误,欢迎指正。

    
    

     

    转载于:https://www.cnblogs.com/jy107600/p/7499158.html

    展开全文
  • 动态规划

    2020-01-11 11:36:47
    由于笔者最近各大小公司中面试都被问及动态规划,所以想重新具体巩固一下什么动态规划。 说起动态规划,便是: 最优子结构: 即一个问题的最优解包含了其子问题的最优解 重叠子问题: 即问题的求解过程中,很...

    由于笔者最近在各大小公司中面试都被问及动态规划,所以想重新具体巩固一下什么是动态规划。

    说起动态规划,便是:
    最优子结构:
    即一个问题的最优解包含了其子问题的最优解
    重叠子问题:
    即在问题的求解过程中,很多子问题的解被多次使用

    总之就是用空间换时间,每个子问题只求解一次,并将其结果保存起来,之后用到的时候直接存取,不重复计算。另外得自底向上的计算,先求子问题的解,最后得到整体问题的解。

    1.最大不下降子序列

    问题描述:从序列中选出若干个数组组成一个新的序列,不改变他们原来的顺序,要求新的序列里xi1xixi+1x_{i-1}≤x_i≤x_{i+1}

    子问题:dp[i]表示前i个元素构成的最长不下降子序列的长度。

    子结构:若最长不下降子序列包括xix_i,则必有一个解包含ai,a2,...,ai1a_i,a_2,...,a_{i-1}的最长不下降子序列

    状态转移方程:dp[i]=max{dp[j], 0<j<i, aj≥ai} + 1

    伪代码为:
    for i from 1 to n
        dp[i]=0;
        for j from 1 to i-1
            if x[j] <=x[i] and dp[j] > dp[i]
                then dp[i]=dp[j];
        dp[i]=dp[i]+1
    时间复杂度:O(n^2)

    2.矩阵连乘

    子结构:若计算A1nA_{1-n}在k处断开矩阵链,即A1n=A1kA(k+1)nA_{1-n}=A_{1-k}*A_{(k+1)-n},则在计算A1nA_{1-n}时,对应于子问题A1kA_{1-k}的解必须是A1kA_{1-k}的最优解,对应于子问题A(k+1)nA_{(k+1)-n}的解必须是A(k+1)nA_{(k+1)-n}的最优解。

    子问题:具有重叠性
    在这里插入图片描述

    动态转移方程:
    在这里插入图片描述

    3.0-1背包问题

    问题描述:给定n种物品和一个背包,物品i的重量是wi,价值vi,背包容量为C。问如何选择装入背包的物品,使装入背包中的物品的总价值最大?对于每种物品总能选择完全装入或不装入,一个物品最多装入一次。

    子问题:每个物品只能选择装或不装,即为二叉树结构
    在这里插入图片描述

    动态转移方程:
    m(i,j):背包容量j,可选物品为xi,xi+1,...,xnx_i,x_{i+1},...,x_n时,问题的最优解,即最大价值为m[i,j]。
    m(n,j)=0, 0≤j<wn
    m(n,j)=vn, j≥wn
    m(i,j)=m(i+1,j), 0≤j<wi
    m(i,j)=max{m(i+1,j), m(i+1, j-wi)+vi}, j≥wi

    4.最长公共子序列

    问题描述:Z是X的子序列也是Y的子序列中最长的一部分

    子结构:X序列长为m,Y序列长为n
    XmYn=Xm1Yn1+1,xm=ynX_mY_n=X_{m-1}Y_{n-1}+1, x_m=y_n
    XmYn=Xm1Yn,xmynzkxmX_mY_n=X_{m-1}Y_{n}, x_m≠y_n,z_k≠x_m
    XmYn=XmYn1,xmynzkynX_mY_n=X_{m}Y_{n-1}, x_m≠y_n,z_k≠y_n

    子问题:每个子问题都有三种情况,即为三叉树
    在这里插入图片描述

    状态转移方程:
    L[i,j] = 0, i=0 or j=0
    L[i,j] = L[i-1,j-1]+1, i,j>0 and xi=yi
    L[i,j] = max{ L[i,j-1], L[i-1,j] }, i,j>0 and xi≠yi

    展开全文
  • 动态规划系列(1)——动态规划入门

    千次阅读 多人点赞 2018-08-01 16:47:32
    你的题目中出现最优、最多、最好等字眼的时候,很可能可以使用动态规划问题来解决了。 那么什么是动态规划(Dynamic Programming)呢?动态规划和分治思想、递归有着千丝万缕的关系。简单来说,分治思想是把一个...

    一般的,我们常用的解决问题的方法有暴力解决法、分而治之、二分法、贪心法和动态规划法。在你遇到一个问题怎么想都想不出其解法的时候,很可能就需要用到动态规划了;在你的题目中出现最优、最多、最好等字眼的时候,很可能可以使用动态规划问题来解决了。

    那么什么是动态规划(Dynamic Programming)呢?动态规划和分治思想、递归有着千丝万缕的关系。简单来说,分治思想是把一个问题分成一个一个的互不相关小问题,小问题再细分直至不可分(类似于把一根木棍切啊切);递归就是在程序运行的过程中调用自身的一种编程技巧;动态规划通过寻找过程状态转移方程,将一个问题分解为子问题求解,但是子问题之间可能会有重复,因此如果单纯的使用递归方法来实现动态规划问题时间复杂度会比较高。不过动态规划问题的本质就是递归,这是因为我们在分析动态规划问题的过程中,需要状态转移方程,这个状态转移方程本质上就是递归。后面实现的过程中是否使用递归只是实现的不同而已,其本质就是递归。

    动态规划有三个最基本的元素:最优子结构、状态转移方程和边界。状态转移方程用于描述将当前状态的解分解为更小状态的关系式;边界即状态转移方程的截止条件;最优子结构即确保通过状态转移方程所选择的子问题也能给出最优的解。

    以最最基础的fibnacci问题为例:其基础的递推关系式为:

    fib(i)=max\left\{\begin{matrix} i & i<2\\ fib(i-1)+fib(i-2) & otherwise \end{matrix}\right.

    如果现在需要计算fib(5),按照规则需要计算fib(4) + fib(3),然后分别计算fib(4)和fib(3),具体的计算过程如下图所示:

    这一个递归的,层层向下的调用过程就是动态规划解fibnacci问题的过程,一般的,动态规划问题的展开图就像上面这样呈树状结构。而这样的结构示意图只是我们分析动态规划问题的第一步(通过写出的状态转移方程对问题进行结构上的分析)。接下来通过编程解决这样一个问题的时候有两种选择:一种是自顶向下,也就是通过递归的方式来解决;一种是自下向上,通过记录每一步的状态量来减少时间复杂度(用空间换时间)。下面分别对这两种方法进行讲解:

    方法一:递归

    采用递归实质上就是按照上图中的二叉树的先序遍历的顺序执行,其中每有一个节点就代表执行一次,因此其时间复杂度是O(2^n),这种递归解法太暴力了,时间复杂度太高。在LeetCode上上传这样的代码即使结果正确也不能Accept。

    int fib(int idx)
    {
        if (idx < 2) {
            return idx;
        }
        
        return fib(idx - 1) + fib(idx - 2);
    
    }

    方法二:添加备忘录的递归

    按照二叉树的递归方法会存在很多重复的计算,如何避免这些重复的计算呢?我们提前申请一个数组,将已经计算过的fib(i)的值存在arr[i]中,这样的做法形象的称为备忘录。在后面调用fib(i)函数时,若arr[i] != -1则代表这个数已经计算过了,直接取其值就好了。如此一来每个数的fib函数只需要计算一次,因此其时间复杂度和空间复杂度均为O(n)。

    // global array
    int arr[100];
    
    int fib(int idx)
    {
        if (idx < 2) {
            return idx;
        }
        
        if (arr[idx] != 0) {
            return arr[idx];
        }
        else {
            arr[idx] = fib(idx - 1) + fib(idx - 2);
            return arr[idx];
        }
    
    }

    方法三:自底向上的迭代法

    采用递归的方法始终会有较大的空间消耗,而采用自底向上的迭代方法可以将空间复杂度降低到O(1)级别。 

    int fib(int idx)
    {
        if (idx < 2) {
            return idx;
        }
        
        int a = 0, b = 1, i= 0;
        while (i != idx) {
            int c = a;
            a = b;
            b = c + b;
            i++;
        }
        
        return a;
    }

     这只是最简单的动态规划为题,举这个例子只是为了直观的介绍动态规划的概念,在后面会介绍一些常见的动态规划问题的解决思路和实现代码,并且难度会有很大程度的提升,从一维问题升级到二级问题。

    展开全文
  • 那么问题来了,什么时候会选择使用dp呢,一般情况下,我们能将问题抽象出来,并且问题满足无后效性,满足最优子结构,并且能明确的找出状态转移方程的话, dp无疑是很好的选择。 无后效性是什么呢,无后效性通俗的
  • 动态规划阶段总结

    2019-03-27 21:30:48
    你的题目中出现最优、最多、最好等字眼的时候,很可能可以使用动态规划问题来解决了。 那么什么是动态规划呢?动态规划和分治思想、递归有着千丝万缕的关系。简单来说,递归就是程序运行的过程中调用自身的一种...
  • 动态规划练习

    2017-03-02 20:57:44
    什么动态规划: 1、本质就是利用申请的空间来记录每一个暴力搜索的计算结果,下次要用结果的时候直接使用,而不再进行重复的递归过程 2、动态规划每一中递归状态的计算顺序,依次进行计算。面试中遇到暴力递归...
  • 动态规划总结

    2012-05-02 21:26:44
    一、为什么使用动态规划? 当回溯效率太低的时候,动态规划是个不错的选择,因为它是不断建立最优状态上的递推,得出最终结果。 二、动态规划两大标志: 1)最优子结构:一个问题的最优解包含子问题的最优解...
  • 动态规划进阶理解

    2020-04-21 13:48:55
    首先,我再说一下为什么我们会做这个题目时候,选择了动态规划呢?除了显而易见的问题(就是一感觉就是动态规划),我们通常会发现有的问题都是很独立的,无向后性和向前性,就是说,我们问题的解决可以分开解决,...
  • python学习动态规划

    2019-09-09 14:54:25
    动态规划什么,意义哪里: 今天花了几个小时,重新理解了一下dp。。。 首先我们要知道为什么使用dp,我们选择dp算法的时候,往往是决策问题上,而且是如果不使用dp,直接暴力效率会很低的情况下选择...
  • 知道如何使用动态规划前,知道何时使用动态规划最重要吧。 如果你要知道最后一天的值,取决于第三天做不做,这就是二叉树的结构,一般涉及到两个选择的,画下的话,可以看到有重叠部分,可以考虑动态规划。 遇到...
  • 1.其本质是利用申请的空间来记录每一个暴力搜索的结果,下次要用结果的时候就可以直接使用,而不需要进行重复的递归过程。 2.动态规划规定每一种递归状态的计算顺序,依次进行计算。 1.动态规划算法是从暴力...
  • 动态规划从入门到精通(一)-入门篇

    万次阅读 多人点赞 2018-04-22 12:16:16
    大三的春招,由于自己的不足,过得十分艰难。...怎么使用动态规划? 让我们一个一个来解决! 1、什么是动态规划? 这里参考百度百科,动态规划是求解决策过程最优化的数学方法。把多阶段过程转...
  • 前言 我们刷leetcode的时候,经常会遇到动态规划类型题目。...动态规划(英语:Dynamic programming,简称 DP),是一种数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相
  • 这个时候我们可以使用动态规划来解决问题;它可以大大提高我们代码的效率.,接下来博主会通过一个经典的案例来带大家浅了解一下动态规划思想 案例 背包问题 1.什么是背包问题 假设有一个背包, 背包的最大容量是15,...
  • 贪心与动态规划的区别

    千次阅读 2015-03-22 10:50:18
    很多同学做动规题的时候,很容易做成贪心,的确,动规和贪心是很相近的,很多时候,动规和贪心没有明显的界限,反而很多时候,我们需要使用贪心的思想,对动规进行优化,不过这也就导致了很多同学分不清什么题...
  • 动态规划是先沿着一条路一条道走到黑,直到尽头,然后末端进行比较,也就是说真正开始进行比较的时候尽头,也就是说这次比较不会对之前的路的选择不会影响,把比较结果存在节点,也就完成了记忆,所以动态规划...
  • 一般都是子问题重叠的时候使用动态规划。下面是一个矩阵连乘的问题。 问题:n个矩阵连乘问题 描述:矩阵连乘满足结合律,n个矩阵连乘时,什么样的结合方式可以使得整个过程中所做的乘法次数最小。 数量化:记 ...
  • 什么时候会选择使用dp呢,一般情况下,我们能将问题抽象出来,并且问题满足无后效性,满足最优子结构,并且能明确的找出状态转移方程的话,dp无疑是很好的选择。 无后效性通俗的说就是只要我们得出了当前状态,而...
  • 什么时候使用动态规划?以下是我的一些理解和心得,如果你感兴趣,就接着往下看吧。 对您有帮助的话记得给我点个赞哟! 动态规划的基本思想 动态规划(Dynamic Programming,DP)算法通常用于求解某种具有最优性质的...
  • 动态规划---01背包与记忆化搜索

    千次阅读 2016-04-09 15:00:13
    因此我们使用动态规划时候,原问题必须是重叠的子问题。运用动态规划设计的算法比一般朴素算法高效很多,因为动态规划不会重复计算已经计算过的子问题。因为动态规划又可以称为“记忆化搜索”。  01背包是介绍...
  • 小结:动态规划

    2019-09-25 18:07:57
    概要: ...下标有时候可以灵活使用!比如mod意义下的dp,倍数什么、可到达性等题目都可以这样做。 如果是线性序列的max{f[k]},k<i这种可以用线段树或bit维护成log或者斜率优化或者决策单调用单...
  • 问题描述 ...一般方法为动态规划后面进行讲解。 递归实现 思路分析 先上一张图 为什么一个背包问题可以画一个树的图? 别急,让我慢慢道来: 图中每个节点代表一种状态,每条边代表一种操作 每个
  • 递归和动态规划 动态规划可以理解为是查表的递归(记忆化)。那么什么是递归?什么是查表(记忆化)? 递归 定义: 递归是指函数的定义中使用函数自身的方法。 算法中使用递归可以很简单地完成一些用循环实现的...
  • DTW算法采用了动态规划DP(dynamic programming)的方法来进行时间规整的计算,可以说,动态规划方法时间规整问题上的应用就是DTW。 为什么需要DTW算法 当两个序列按照时间步t完全对齐的时候,我们可以直接使用ED...
  •  虽然我们(一)中讨论过动态规划的装配线问题,但是究竟什么时候使用动态规划?那么我们就要清楚动态规划方法的最优化问题中的两个要素:最优子结构和重叠子问题。  1、最优子结构  1)如果问题的一个最优解...
  • 既然是使用动态规划,那么有以下几点: 维护什么:维护iMax和iMin,分别代表包含当前值的子数组的最大乘积 & 最小乘积 什么时候转移:负数(iMax & iMin互换) 0的时候呢?由于乘积怎么都是0,所以直接...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 141
精华内容 56
关键字:

在什么时候使用动态规划