精华内容
下载资源
问答
  • 2019-10-27 11:00:24

    1.序

    近期笔者会写一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。

    2.动态规划的基本概念[^1]

    在学习动态规划之前,先思考这样一个问题:什么是动态规划?为什么叫动态规划?
    当读者在试图探索这个问题的时候,不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的,应用于工程领域。
    动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

    所谓多阶段决策过程是指这样一类决策过程:它可以把一一个复杂问题按时间(或空间)分成若干个阶段,每个阶段都需要作出决策,
    以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何,不但与该阶段的经济效果有关,
    还影响以后各阶段的经济效果,可见这类多阶段决策问题是一个动态的问题,因此,处理的方法称为动态规划方法。然而,动态
    规划也可以处理一些本来与时间没有关系的静态模型,这只要在静态模型中人为地引入“时间”因素,分成时段,就可以把它看作
    是多阶段的动态模型,用动态规划方法去处理。
    

    简言之,多阶段决策过程是指这样的一类特殊的活动过程:问题可以按时间顺序分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。
    下面举例说明什么是多阶段决策问题。
    例1(最短路线问题)在线路网络图1中,从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离,为使总运费最少,必须找出一条由A至E总里程最短的路线。
    在这里插入图片描述

    图1

    为了找到由A至E的最短线路,可以将该问题分成A—B—C—D—E 4个阶段,在每个阶段都需要作出决策,即在A点需决策下一步到B1还是到B2或B3;同样,若到达第二阶段某个状态,比如B1 ,需决定走向C1还是C2 ;依次类推,可以看出:各个阶段的决策不同,由A至E的路线就不同,当 从某个阶段的某个状态出发作出一个决策,则这个决策不仅影响到下一个阶段的距离,而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策,使这些决策序列所决定的一条路线对应的总路程最短。

    3.动态规划算法的基本思想[^2]

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。
    在这里插入图片描述

    图2

    但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
    如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
    在这里插入图片描述

    图3

    4.动态规划的求解步骤[^2]

    a. 找出最优解的性质,并刻划其结构特征。
    b. 递归地定义最优值。
    c. 以自底向上的方式计算出最优值。
    d. 根据计算最优值时得到的信息,构造最优解

    5.动态规划算法的基本要素[^2]

    5.1 最优子结构

    • 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质
    • 在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。
    • 利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

    注意:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)

    5.2 重叠子问题

    • 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
    • 动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。
    • 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。
      在这里插入图片描述
      图4

    6.一些经典的动态规划问题

    题目描述:
    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

    示例 1:

    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    

    示例 2:

    输入: "cbbd"
    输出: "bb"
    

    分析:
    一个问题要使用动态规划求解,一定要满足【最优子结构】,只有满足最优子结构,才能通过子问题的解 构造出 整个问题的解。

    在编码时,一般采用【备忘录】或 dp table来实现。
    最关键的要找出:该问题的递推关系式(状态转移方程)

    假设dp[i][j]=true,表示字符串s从s[i]到s[j]的子串为最长回文子串
    反之false.

    考虑 abcba 这个示例。如果我们已经知道 bca 是回文,那么要判断 abcba 是不是回文串,只需判断它的左首字母和右尾字母是否相等。这里左=右=a,因此abcba 是回文串

    从这里我们可以归纳出状态转移方程
    dp[i][j] = true
    前提是
    dp[i+1][j-1]为true,且 s[i] == s[j]

    #include <iostream>
    using namespace std;
    class MySolution {
    public:
        string longestPalindrome(string s) {
    
            int len = s.size();
            if (len < 2)
                return s;
            //bool dp[len][len];
            bool** dp;
            dp = new bool* [len];
            for (int i = 0; i < len; i++)
                dp[i] = new bool[len];//分配了len行len列的二维数组空间
        
            int max_len=1;//最大回文串长度
            int max_left;//最长回文串的起始位置
            for (int j = 0; j < len; j++)
            {
                for (int i = 0; i < j; i++)
                {
                    if (s[j] != s[i])
                        dp[i][j] = false;
                    else if (j - i < 3) // (j-1)-(i+1)+1< 2 即表明dp[i][j]是回文串
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];//s[i]==s[j]
                    if (j - i + 1 > max_len && dp[i][j])
                    {
                        max_len = j - i + 1;
                        max_left = i;
                    }
    
                }
            }
            return s.substr(max_left, max_len);
            // 用完要释放:
            for (int i = 0; i < len; i++)
            {
                delete[] dp[i]; 
                delete[]dp;
            }   
        }
    };
    int main()
    {
        MySolution sl;
        string s = sl.longestPalindrome("abcdedcabcdefggfedcba");
        cout << s << endl;
    }
    

    参考文献
    [1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html
    [2]引用自老师的课件

    更多相关内容
  • 动态规划算法解决背包问题

    千次阅读 2021-01-30 15:06:42
    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从子问题解得到原问题解。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用...

    一、动态规划算法概述

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从子问题解得到原问题解。

    在这里插入图片描述

    但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解极值问题时,有些子问题被重复计算了许多次。

    在这里插入图片描述

    如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。

    在这里插入图片描述

    动态规划 VS 分治法

    • 相同点:基本思想均是将原问题分解成若干个子问题,先求子问题,然后从子问题的解得到原问题的解;
    • 不同点:
      • 适用于动态规划求解的问题,分解得到的子问题往往不是互相独立的;
      • 动态规划为自底向上,而分治法为自顶向下。

    当分解出的子问题不相互独立的话,若使用分治法来求解此类问题,会导致使用指数级的运行时间,而子问题的个数只有多项式量级。所以,此类问题不适合使用分治法。

    动态规划是如何减少对重复子问题求解的呢?

    答案是保存已求解的子问题的解,在需要时找出,从而避免大量的重复计算得到多项式的运行时间;通常用一个表来记录所有已解决的子问题。

    动态规划算法通常用于求解具有某种最优性质的问题

    二、背包问题

    2.1 什么是背包问题

    今年的年会,聪明大方的老板为了激励员工,决定买三种类型的奖品奖励给勤奋的员工小王。

    在这里插入图片描述

    为了让自己不至于放血太多又不会显得太抠门,美其名曰考验员工小王的智商。机智的老板想到了一个好法子:给小王发一个最大能装下 4 磅物品的背包,只有装到背包中的物品才归属于小王。

    如果你是员工小王,怎么装才能得到最大的物品价值呢?

    2.2 背包问题思路分析

    首先,最容易想到的方法,就是计算出各种可能的奖品组合的情况,找出价值最高的组合放入到背包中。对于三种奖品,共有 8 种的组合,对于四种奖品,共有 16 种组合。每增加一种奖品,需要计算的组合数都将翻倍。如果明年老板决定奖励十一种奖品给小王,那小王最好还是放弃奖品算了。我们可以看到,这种算法的时间复杂度为 O(2ⁿ),效率较低。

    如何找到最优解呢?答案是使用动态规划

    对于背包问题,可以先解决小背包(子背包)的问题,然后逐步解决原来的问题。

    在这里插入图片描述

    每个动态规划算法都从一个网格开始,背包问题的网格如下。

    在这里插入图片描述

    网格的各行为奖品,各列为不同容量(1~4磅)的背包。所有这些列都是必要的,因为它们将用于计算子背包中的物品价值。

    第一步:

    我们首先假设可选择的奖品只有吉他(1 磅)。当背包的容量为 1 时,刚好放下一个吉他,此时背包价值为 1500。当背包的容量为 2、3、4 时,由于可选的商品只有吉他且同样的奖品只能拿一件,因此即便会使背包的空间浪费,背包中仍然是只能放一个吉他,背包中的价值仍然为 1500。

    在这里插入图片描述

    第二步:

    我们再假设可选的商品只有吉他(1 磅)和音响(4 磅)。当背包的容量为 1、2、3 时,由于音响的重量为 4,因此无法放入到背包中,背包中只能放入一个吉他。

    在这里插入图片描述

    当背包的容量为 4 时,刚好等于音响的重量。这个时候有两个选择:一是只放入一个吉他;二是只放入一个音响。由于音响的价值为 3000,大于吉他的价值,因此选择将音响放入背包,此时背包中的价值为 3000。

    在这里插入图片描述

    第三步:

    我们在假设可选择商品有吉他(1 磅)、音响(4 磅)、笔记本电脑(3 磅)。当背包的容量为 1、2 时,毫无疑问,背包中只能放一个吉他。此时背包的价值为 1500。

    在这里插入图片描述

    当背包的容量为 3 时,有两种选择:一是只放入一个吉他;二是只放入一个电脑。由于电脑的价值高于吉他,因此将电脑放入。此时背包的价值为 2000。

    在这里插入图片描述

    当背包的容量为 4 时,仍然有两种选择:一是放入一个吉他和电脑;二是只放入一个音响。由于吉他和电脑的总价值高于音响的价值,因此将吉他和电脑放入。此时背包的价值为 1500 + 2000 = 3500。

    在这里插入图片描述

    因此,将吉他和笔记本电脑装入背包时价值最高,这就是小王的最优解。

    总结:

    那么这个过程,如何用数学公式表达呢?

    我们首先约定一共有 N 件物品,第 i 件物品的重量为 w[i],价值为 v[i],背包的承载上限为 W。再约定一个状态 cell[i][j] 表示将前 i 件(这里的前 i 件指的是有 i 件可选)物品装进限重为 j 的背包可以获得的最大价值(0<=i<=N0<=j<=W)。

    那么我们可以将 cell[0][0...W] 初始化为 0,表示将前 0 个物品装入书包的最大价值为 0。

    i>0 时,cell[i][j] 有两种情况:

    1. 不装入第 i 件物品,则背包最大价值就是相同背包容量下只有 i-1 件物品可选时的最大价值,即 cell[i-1][j]
    2. 装入第 i 件物品(若背包容量够),则最大价值为当前物品价值加背包剩余容量的最大价值,即 v[i] + cell[i-1][j-w[i]]

    那么 cell[i][j] 的值,就是这两种情况下的最大值。由此可以得到方程:
    c e l l [ i ] [ j ] = m a x { c e l l [ i − 1 ] [ j ] c e l l [ i − 1 ] [ j − w [ i ] ] + v [ i ] j > = w [ i ] cell[i][j] = max \left \{\begin {aligned}&cell[i-1][j]\\&cell[i-1][j-w[i]] + v[i]\end{aligned}\right. \quad\quad j>=w[i] cell[i][j]=max{cell[i1][j]cell[i1][jw[i]]+v[i]j>=w[i]
    求得所有的 cell[i][j] 之后,最后一个值就是背包问题的最大值。

    2.3 背包问题代码实现

    public static void main(String[] args) {
        int[] w = {0, 1, 4, 3};    // 物品的重量
        int[] v = {0, 1500, 3000, 2000};    // 物品的价值
    
        int num = w.length; // 物品的数量可能的个数 (0~3,共 3 个)
        int weight = 5; // 背包的容量可能的个数 (0~4,共 5 个)
    
        int[][] cell = new int[num][weight];    // cell[i][j] 表示前i个物品可选,背包容量为j时的最大价值
        int[][] record = new int[num][weight];  // record[i][j] 用于标记第i个物品有没有放入容量为j的背包
    
        for (int i=1; i<num; i++){  // 遍历物品
            for (int j=1; j<weight; j++){   // 遍历背包容量
                if (w[i]>j){    // 如果当前物品重量大于背包容量
                    cell[i][j] = cell[i-1][j];  // 不装入
                }else{  // 如果当前物品重量小于等于背包容量
                    int value_1 = cell[i-1][j]; // 不放入第 i 个物品的背包价值
                    int value_2 = v[i] + cell[i-1][j-w[i]]; // 放入第 i 个物品后的价值
                    /* 把最大价值放入背包 */
                    if (value_1 > value_2){
                        cell[i][j] = value_1;
                    }else{
                        cell[i][j] = value_2;
                        record[i][j] = 1;   // 用于标记在本网格放入了第 i 个物品
                    }
                }
            }
        }
    
        // 最后一个网格就是最大价值
        System.out.println("背包价值为:" + cell[num-1][weight-1]);
    
        // 由于最后一个网格就是最大价值
        // 因此,逆序遍历 record 找到最后一个放入的物品,然后找到剩余空间价值是放入第几个物品
        int i = record.length-1;
        int j = record[0].length-1;
        while (i > 0 && j > 0){
            if (record[i][j] == 1){
                System.out.printf("放入了第 %d 个商品\n", i);
                j = j - w[i];   // 背包剩余容量
            }
            i--;
        }
    }
    

    运行结果如下:

    在这里插入图片描述
    【注】:本文的图大多出自《算法图解》。

    展开全文
  • 动态规划算法

    千次阅读 2022-01-19 11:12:57
    1. 应用场景-背包问题 ...动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划求解的问题

    1. 应用场景-背包问题

    背包问题:有一个背包,容量为4磅 , 现有如下物品
    请添加图片描述
    要求如下:

    1. 要求达到的目标为装入的背包的总价值最大,并且重量不超出
    2. 要求装入的物品不能重复

    2. 动态规划算法介绍

    1. 动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法

    2. 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

    3. 与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 )

    4. 动态规划可以通过填表的方式来逐步推进,得到最优解.

    3. 思路

    算法的主要思想,利用动态规划来解决。每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i]、w[i]分别为第i个物品的价值和重量,C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。

    构建表格
    请添加图片描述

    上图中:第一行全部为0,表示前0个物品中能够装入容量为1,2,3,4磅的物品的价值都为0,因为前0个物品就是一个物品都没有,所以,无论背包有多少磅,其装入的价值都为0。第一列全部为0,就是背包可以装入的重量为0磅,所以什么物品都不能放入其中。

    请添加图片描述
    上图中,v[1][1]中背包能够承受1磅,在前一个物品中选择,前一个物品就只有吉他,所以就只能选择吉他进入包中,价值为v[1][1]=1500。v[1][2]中背包能够装入2磅,从前一个物品中选择,所以还是只能选择吉他 v[1][2] = 1500。注意不能重复放入物品,所以v[1][2] = 1500 而不是3000。v[1][3],v[1][4]同理。

    请添加图片描述
    上图中,v[2][1]中,背包能够承受1磅,可以选择的物品是前两个物品即吉他(1磅)和音响(4磅),所以只能选择吉他,所以v[2][1]的值是拷贝自v[1][1]的值。 即v[2][1]的上一格。 v[2][2]中,背包能够承受2磅,还是只能存放吉他,所以v[2][2]的值是拷贝自v[1][2]的值。 v[2][3]同理,v[2][4]中,背包能够承受4磅,吉他和音响不能同时入包,只能选择一个,所以选择价值大的音响。所以v[2][4] = 3000.

    请添加图片描述
    上图中,v[3][1]只能承受1磅,从前三个物品中选择(吉他,音响,电脑),由于只能承受1磅,所以只能选择吉他,所以v[3][1] = 1500 拷贝自v[2][1]. v[3][2]同理。v[3][3]中能够承受3磅,所以选择电脑,所以v[3][3] = 2000. v[3][4]中可以承受4磅,所以可以选择吉他和电脑或者只选择音响,因为吉他和电脑的总价值比音响大,所以选择吉他和电脑,所以v[3][4] = 3500.

    总结
    算法的主要思想,利用动态规划来解决。每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i]、w[i]分别为第i个物品的价值和重量,C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。

    (1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0

    (2) 当w[i]> j 时:v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时,就直接使用上一个单元格的装入策略

    (3) 当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 当准备加入的新增的商品的容量小于等于当前背包的容量.

    装入的方式:

    v[i-1][j]: 就是上一个单元格的装入的最大值

    v[i] : 表示当前商品的价值

    v[i-1][j-w[i]] : 装入i-1商品,到剩余空间j-w[i]的最大值

    4. 代码实现

    public class KnapsackProblem {
        public static void main(String[] args) {
            int[] w = {1, 4, 3}; // 保存物品的数量
            int[] val = {1500, 3000, 2000}; // 物品的价值
            int m = 4; // 背包的容量
            int n = val.length; // 物品的个数
            int[][] v = new int[n + 1][m + 1]; // 二维数组 v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。
    
    
            // 初始化第一行和第一列
            for (int i = 0; i < v.length; i++) {
                v[i][0] = 0;
            }
            for (int i = 0; i < v[0].length; i++) {
                v[0][i] = 0;
            }
    
            // 开始处理
            for (int i = 1; i < v.length; i++) {
                for (int j = 1; j < v[0].length; j++) {
                    // 公式
                    if (w[i - 1] > j) {
                        v[i][j] = v[i - 1][j];
                    } else {
                        v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    }
                }
            }
    
    
            // 输出二维数组
            for (int i = 0;i<v.length;i++){
                System.out.println(Arrays.toString(v[i]));
            }
    
        }
    }
    
    

    请添加图片描述

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

    千次阅读 多人点赞 2020-04-09 07:59:47
    简单总结一下,最优子结构,状态转移方程,重叠子问题就是动态规划的三要素,这其中定义子问题的状态与写出状态转移方程是解决动态规划最为关键的步骤,状态转移方程如果定义好了,解决动态规划基本不是问题了。...

    摘要

    动态规划(dynamic programming,简称dp)是工程中非常重要的解决问题的思想,从我们在工程中地图软件上应用的最短路径问题,再在生活中的在淘宝上如何凑单以便利用满减券来最大程度地达到我们合理薅羊毛的目的,很多时候都能看到它的身影。不过动态规划对初学者来说确实比较难,dp状态,状态转移方程让人摸不着头脑,网上很多人也反馈不太好学,其实就像我们之前学递归那样,任何算法的学习都是有它的规律和套路的,只要掌握好它的规律及解题的套路,再加上大量的习题练习,相信掌握它不是什么难事,本文将会用比较浅显易懂地讲解来帮助大家掌握动态规划这一在工程中非常重要的思想,相信看完后,动态规划的解题套路一定能手到擒来(文章有点长,建议先收藏再看,看完后一定会对动态规划的认知上升到一个台阶!)

    本文将会从以下角度来讲解动态规划:

    • 什么是动态规划
    • 动态规划从入门到进阶
    • 再谈动态规划

    什么是动态规划

    以下是我综合了动态规划的特点给出的动态规划的定义:动态规划是一种多阶段决策最优解模型,一般用来求最值问题,多数情况下它可以采用自下而上的递推方式来得出每个子问题的最优解(即最优子结构),进而自然而然地得出依赖子问题的原问题的最优解。

    划重点:

    • 多阶段决策,意味着问题可以分解成子问题,子子问题,。。。,也就是说问题可以拆分成多个子问题进行求解
    • 最优子结构,在自下而上的递推过程中,我们求得的每个子问题一定是全局最优解,既然它分解的子问题是全局最优解,那么依赖于它们解的原问题自然也是全局最优解。
    • 自下而上,怎样才能自下而上的求出每个子问题的最优解呢,可以肯定子问题之间是有一定联系的,即迭代递推公式,也叫「状态转移方程」,要定义好这个状态转移方程, 我们就需要定义好每个子问题的状态(DP 状态),那为啥要自下而上地求解呢,因为如果采用像递归这样自顶向下的求解方式,子问题之间可能存在大量的重叠,大量地重叠子问题意味着大量地重复计算,这样时间复杂度很可能呈指数级上升(在下文中我们会看到多个这样重复的计算导致的指数级的时间复杂度),所以自下而上的求解方式可以消除重叠子问题。
      简单总结一下,最优子结构,状态转移方程,重叠子问题就是动态规划的三要素,这其中定义子问题的状态与写出状态转移方程是解决动态规划最为关键的步骤,状态转移方程如果定义好了,解决动态规划就基本不是问题了。

    既然我们知道动态规划的基本概念及特征,那么怎么判断题目是否可以用动态规划求解呢,其实也很简单,当问题的定义是求最值问题,且问题可以采用递归的方式,并且递归的过程中有大量重复子问题的时候,基本可以断定问题可以用动态规划求解,于是我们得出了求解动态规划基本思路如下(解题四步曲)

    判断是否可用递归来解,可以的话进入步骤 2

    • 分析在递归的过程中是否存在大量的重复子问题
    • 采用备忘录的方式来存子问题的解以避免大量的重复计算(剪枝)
    • 改用自底向上的方式来递推,即动态规划

    接下来我们会做几道习题来强化一下大家对这些概念及动态规划解题四步曲的理解,每道题我们都会分别用递归,递归+备忘录,动态规划来求解一遍;

    动态规划从入门到进阶

    入门题:斐波那契数列

    接下来我们来看看怎么用动态规划解题四步曲来解斐波那契数列

    画外音:斐波那契数列并不是严格意义上的动态规划,因为它不涉及到求最值,用这个例子旨在说明重叠子问题与状态转移方程

    1、判断是否可用递归来解 显然是可以的,递归代码如下

    public static int fibonacci(int n) {
        if (n == 1) return1;
        if (n == 2) return2;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
    

    2、分析在递归的过程中是否存在大量的重复子问题

    怎么分析是否有重复子问题,画出递归树
    在这里插入图片描述
    可以看到光是求 f(6),就有两次重复的计算, f(4) 求解了两次,f(3) 求解了两次,时间复杂度是指数级别,递归时间复杂度怎么看,解决每个子问题需要的时间乘以子问题总数,每个子问题需要的时间即 f(n) = f(n-1) + f(n-2) 只做了一次加法运算,子问题的个数有多少呢,每个问题一分为二,是个二叉树,可以看到第一层 1 个,第二层 2 个,第三层 4 个,即 1 + 2 + 2^2 + … 2n,所以总的来说时间复杂度是)O(2n),是指数级别。
    画外音:求解问题 f(6),转成求 f(5),f(4),从原问题出发,分解成求子问题,子问题再分解成子子问题,。。。,直到再也不能分解,这种从 原问题展开子问题进行求解的方式叫自顶向下
    3、采用备忘录的方式来存子问题的解以避免大量的重复计算 既然以上中间子问题中存在着大量的重复计算,那么我们可以把这些中间结果给缓存住(可以用哈希表缓存),如下

    public static int fibonacci(int n) {
        if (n = 1) return1;
        if (n = 2) return2;
        if (map.get(n) != null)  {
            return map.get(n);
        }
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        map.put(n, result);
        return result;
    }
    

    这么缓存之后再看我们的递归树
    在这里插入图片描述
    可以看到通过缓存中间的数据,做了大量地剪枝的工作,同样的f(4),f(3),f(2),都只算一遍了,省去了大量的重复计算,问题的规模从二叉树变成了单链表(即 n),时间复杂度变成了 O(n),不过由于哈希表缓存了所有的子问题的结果,空间复杂度是 O(n)。
    4、改用自底向上的方式来递推,即动态规划 我们注意到如下规律

    f(1) = 1
    f(2) = 2
    f(3) = f(1) + f(2) = 3
    f(4) = f(3) + f(2) = 5
    ....
    f(n) = f(n-1) + f(n-2)
    

    所以只要依次自底向上求出 f(3),f(4),…,自然而然地就求出了 f(n)
    在这里插入图片描述
    画外音:从最终地不能再分解的子问题根据递推方程(f(n) = f(n-1) + f(n-2))逐渐求它上层的问题,上上层问题,最终求得一开始的问题,这种求解问题的方式就叫自底向上。

    f(n) 就是定义的每个子问题的状态(DP 状态),f(n) = f(n-1) + f(n-2) 就是状态转移方程,即 f(n) 由 f(n-1), f(n-2) 这两个状态转移而来,由于每个子问题只与它前面的两个状态,所以我们只要定义三个变量,自底向上不断循环迭代即可,如下

    public int f(int n) {
        if (n == 1) return1;
        if (n == 2) return2;
        int result = 0;
        int pre = 1;
        int next = 2;
        
        for (int i = 3; i < n + 1; i ++) {
            result = pre + next;
            pre = next;
            next = result;
        }
        return result;
    }
    

    这样时间复杂度虽然还是O(n),但空间复杂度只由于只定义了三个变量(result,pre,next)所以是常量 O(1)。

    通过简单地斐波那契的例子,相信大家对自底向上,DP 状态, DP 转移方程应该有了比较深入地认识,细心的同学一定发现了最优子结构怎么没有,因为前面我们也说了,斐波那契数列并不是严格意义上的动态规划,只是先用这个简单地例子来帮助大家了解一下一些基本的概念。在之后的习题中我们将会见识到真正的动态规划

    小试牛刀:三角形的最小路径和
    在这里插入图片描述
    如图示,以上三角形由一连串的数字构成,要求从顶点 2 开始走到最底下边的最短路径,每次只能向当前节点下面的两个节点走,如 3 可以向 6 或 5 走,不能直接走到 7。

    在这里插入图片描述
    如图示:从 2 走到最底下最短路径为 2+3+5+1 = 11,即为我们所求的

    首先我们需要用一个二维数组来表示这个三个角形的节点,用二维数组显然可以做到, 第一行的 2 用 a[0][0] 表示,第二行元素 3, 4 用 a[1][0],a[1][1],依此类推。
    在这里插入图片描述
    定义好数据结构之后,接下来我们来看看如何套用我们的动态规划解题套路来解题

    1、 判断是否可用递归来解

    如果用递归,就要穷举所有的路径和,最后再求所有路径和的最小值,我们来看看用递归怎么做。

    对于每个节点都可以走它的左或右节点,假设我们定义 traverse(i, j) 为节点 a[i][j] 下一步要走的节点,则可以得出递归公式的伪代码如下

    traverse(i, j) = {
        traverse(i+1, j);    向节点i,j 下面的左节点走一步
        traverse(i+1, j+1);    向节点i,j 下面的右节点走一步
    }
    

    什么时候终止呢,显然是遍历到三角形最后一条边的节点时终止,发现了吗,对每个节点来说,在往下(无论是往左还是往右)遍历的过程中,问题规模不断地在缩小,也有临界条件(到达最后一条边的节点时终止),分解的子问题也有相同的解决问题的思路(对于每个节点的遍历都是往左或往右),符合递归的条件!于是我们得到递归代码如下

    privatestaticint[][] triangle = {
                {2, 0, 0, 0},
                {3, 4, 0, 0},
                {6, 5, 7, 0},
                {4, 1, 8, 3}
    };
    
    public static int traverse(int i, int j) {
        int totalRow = 4; // 总行数
        if (i >=  totalRow - 1) {
            return0;
        }
        // 往左下节点走时
        int leftSum = traverse(i+1, j) + triangle[i+1][j];
        // 往右下节点走时
        int rightSum = traverse(i+1, j+1) + triangle[i+1][j+1];
        // 记录每个节点往左和往右遍历的路径和的最小值
        return Math.min(leftSum, rightSum);
    }
    
    public static  void main(String[] args)  throws Throwable {
        int sum = traverse(0, 0) + triangle[0][0];
        System.out.println("sum = " + sum);
    }
    

    对于每个节点,要么向左或向右,每个问题都分解成了两个子问题,和斐波那契数列一样,如果画出递归树也是个二叉树,所以时间复杂度是 O(2^n),也是指数级别。

    2、分析在递归的过程中是否存在大量的重复子问题

    为啥时间复杂度是指数级别呢,我们简单分析一下:
    在这里插入图片描述
    对于节点 3 和 4 来说,如果节点 3 往右遍历, 节点 4 往左遍历,都到了节点 5,节点 5 往下遍历的话就会遍历两次,所以此时就会出现重复子问题

    3、采用备忘录的方式来存子问题的解以避免大量的重复计算(剪枝)

    既然出现了,那我们就用备忘录把中间节点缓存下来

    于是我们的代码改为如下所示

    privatestaticint[][] triangle = {
                {2, 0, 0, 0},
                {3, 4, 0, 0},
                {6, 5, 7, 0},
                {4, 1, 8, 3}
        };
    
    // 记录中间状态的 map
    privatestatic HashMap<String, Integer> map = new HashMap();
    
    public static int traverse(int i, int j) {
        String key = i + "" + j;
        if (map.get(key) != null) {
            return map.get(key);
        }
    
        int totalRow = 4; // 总行数
        if (i >=  totalRow - 1) {
            return0;
        }
        // 往左下节点走时
        int leftSum = traverse(i+1, j) + triangle[i+1][j];
        // 往右下节点走时
        int rightSum = traverse(i+1, j+1) + triangle[i+1][j+1];
        // 记录每个节点往左和往右遍历的路径和的最小值
        int result = Math.min(leftSum, rightSum);
        map.put(key, result);
        return result;
    }
    

    这么一来,就达到了剪枝的目的,避免了重复子问题,时间复杂度一下子下降到 O(n), 空间复杂度呢,由于我们用哈希表存储了所有的节点的状态,所以空间复杂度是 O(n)。

    4、改用自底向上的方式来递推,即动态规划

    重点来了,如何采用自底向上的动态规划来解决问题呢? 我们这么来看,要求节点 2 到底部边的最短路径,只要先求得节点 3 和 节点 4 到底部的最短路径值,然后取这两者之中的最小值再加 2 不就是从 2 到底部的最短路径了吗,同理,要求节点 3 或 节点 4 到底部的最小值,只要求它们的左右节点到底部的最短路径再取两者的最小值再加节点本身的值(3 或 4)即可。

    我们知道对于三角形的最后一层节点,它们到底部的最短路径就是其本身,于是问题转化为了已知最后一层节点的最小值怎么求倒数第二层到最开始的节点到底部的最小值了。先看倒数第二层到底部的最短路径怎么求
    在这里插入图片描述
    同理,第二层对于节点 3 ,它到最底层的最短路径转化为了 3 到 7, 6 节点的最短路径的最小值,即 9, 对于节点 4,它到最底层的最短路径转化为了 4 到 6, 10 的最短路径两者的最小值,即 10。

    在这里插入图片描述
    接下来要求 2 到底部的路径就很简单了,只要求 2 到节点 9 与 10 的最短路径即可,显然为 11。
    在这里插入图片描述
    于是最终的 11 即为我们所求的值,接下来我们来看看怎么定义 DP 的状态与状态转移方程。我们要求每个节点到底部的最短路径,于是 DP 状态 DP[i,j] 定义为 i,j 的节点到底部的最小值,DP状态转移方程定义如下:

    DP[i,j] = min(DP[i+1, j], D[i+1, j+1]) + triangle[i,j]
    

    这个状态转移方程代表要求节点到最底部节点的最短路径只需要求左右两个节点到最底部的最短路径两者的最小值再加此节点本身!仔细想想我们上面的推导过程是不是都是按这个状态转移方程推导的,实在不明白建议多看几遍上面的推导过程,相信不难明白。

    DP 状态 DP[i,j] 有两个变量,需要分别从下而上,从左到右循环求出所有的 i,j, 有了状态转移方程求出代码就比较简单了,如下

    privatestaticint[][] triangle = {
            {2, 0, 0, 0},
            {3, 4, 0, 0},
            {6, 5, 7, 0},
            {4, 1, 8, 3}
    };
    public static int traverse() {
        int ROW = 4;
        int[] mini = triangle[ROW - 1];
        // 从倒数第二行求起,因为最后一行的值本身是固定的
        for (int i = ROW - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[j].length; j++) {
                mini[j] = triangle[i][j] + Math.min(mini[j], mini[j+1]);
            }
        }
        return mini[0];
    }
    
    public static  void main(String[] args)  throws Throwable {
        int minPathSum = traverse();
        System.out.println("sum = " + minPathSum);
    }
    

    可能有一些人对 mini 数组的定义有疑问,这里其实用了一个比较取巧的方式,首先我们定义 mini 的初始值为最后一行的节点,因为最后一行的每个节点的 DP[i,j] 是固定值,只要从倒数第二行求起即可,其次我们知道每个节点到底部的最短路径只与它下一层的 D[I+1,j], D[i+1, j] 有关,所以只要把每一层节点的 DP[i,j] 求出来保存到一个数组里即可,就是为啥我们只需要定义一下 mini 一维数组的原因
    **加粗样式**
    如图示:要求节点 2 到底部的最短路径,它只关心节点 9, 10,之前层数的节点无需再关心!因为 9,10 已经是最优子结构了,所以只保存每层节点(即一维数组)的最值即可!

    当自下而上遍历完成了,mini[0] 的值即为 DP[0,0],即为节点 2 到 底部的最短路径。mini 的定义可能有点绕,大家可以多思考几遍,当然,你也可以定义一个二维数组来保存所有的 DP[i,j],只不过多耗些空间罢了。

    这里我们再来谈谈最优子结构,在以上的推导中我们知道每一层节点到底部的最短路径依赖于它下层的左右节点的最短路径,求得的下层两个节点的最短路径对于依赖于它们的节点来说就是最优子结构,最优子结构对于子问题来说属于全局最优解,这样我们不必去求节点到最底层的所有路径了,只需要依赖于它的最优子结构即可推导出我们所要求的最优解,所以最优子结构有两层含义,一是它是子问题的全局最优解,依赖于它的上层问题只要根据已求得的最优子结构推导求解即可得全局最优解,二是它有缓存的含义,这样就避免了多个依赖于它的问题的重复求解(消除重叠子问题)。

    总结:仔细回想一下我们的解题思路,我们先看了本题是否可用递归来解,在递归的过程中发现了有重叠子问题,于是我们又用备忘录来消除递归中的重叠子问题,既然我们发现了此问题可以用递归+备忘录来求解,自然而然地想到它可以用自底向上的动态规划来求解。是的,求解动态规划就按这个套路来即可,最重要的是要找出它的状态转移方程,这需要在自下而上的推导中仔细观察。

    进阶:凑零钱

    给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。输入: coins =
    [1, 2, 5], amount = 11,输出: 3 解释: 11 = 5 + 5 + 1 输入: coins = [2],
    amount = 3,输出: -1

    来套用一下我们的动态规划解题四步曲

    一、判断是否可用递归来解

    对于 amount 来说,如果我们选择了 coins 中的任何一枚硬币,则问题的规模(amount)是不是缩小了,再对缩小的 amount 也选择 coins 中的任何一枚硬币,直到再也不能选择(amount <= 0, amount = 0 代表有符合条件的解,小于0代表没有符合条件的解),从描述中我们可以看出问题可以分解成子问题,子问题与原问题具有相同的解决问题的思路,同时也有临界条件,符合递归的条件,由此可证可以用递归求解,接下来我们来看看,如何套用递归四步曲来解题

    1、定义这个函数,明确这个函数的功能,函数的功能显然是给定一个 amount,用定义好的 coins 来凑,于是我们定义函数如下

    private static int f(int amount, int[] coins) {
    }
    

    2、寻找问题与子问题的关系,即递推公式 这题的递推关系比较难推导,我们一起看下,假设 f(amount, coins) 为零钱 amount 的所需要的最少硬币数,当选中了coins 中的第一枚硬币之后(即为 coins[0]),则需再对剩余的 amount - coins[0] 金额求最少硬币数,即调用 f(amount - coins[0], coins) ,由此可知当选了第一枚硬币后的递推公式如下`

    f(amount, coins) = f(amount-coins[0]) + 1 (这里的 1 代表选择了第一枚硬币)
    

    如果选择了第二,第三枚呢,递推公式如下

    f(amount, coins) = f(amount-coins[1]) + 1 (这里的 1 代表选择了第二枚硬币)
    f(amount, coins) = f(amount-coins[2]) + 1 (这里的 1 代表选择了第三枚硬币)
    

    我们的目标是求得所有以上 f(amount, coins) 解的的最小值,于是可以得到我们的总的递推公式如下

    f(amount, coins) = min{ f(amount - coins[i]) + 1) }, 其中 i 的取值为 0 到 coins 的大小,coins[i] 表示选择了此硬币, 1 表示选择了coins[i]  这一枚硬币
    

    3、将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中

    得出了递推公式用代码实现就简单了,来简单看一下

    publicclass Solution {
    
        private static int exchange(int amount, int[] coins) {
    
            // 说明零钱刚好凑完
            if (amount == 0) {
                return0;
            }
    
            // 说明没有满足的条件
            if (amount < 0) {
                return -1;
            }
    
            int result = Integer.MAX_VALUE;
            for (int i = 0; i < coins.length; i++) {
                int subMin = exchange(amount - coins[i], coins);
                if (subMin == -1) continue;
                result = Math.min(subMin + 1, result);
            }
    
            // 说明没有符合问题的解
            if (result == Integer.MAX_VALUE) {
                return -1;
            }
    
            return result;
        }
    
        public static  void main(String[] args)  throws Throwable {
            int amount = 11;
            int[] coins = {1,2,5};
            int result = exchange(amount, coins);
            System.out.println("result = " + result);
        }
    }
    

    4、计算时间复杂度 这道题的时间复杂度很难看出来,一般看不出来的时候我们可以画递归树来分析,针对 amount = 11 的递归树 如下
    在这里插入图片描述
    前文我们说到斐波那契的递归树是一颗二叉树,时间复杂度是指数级别,而凑零钱的递归树是一颗三叉树 ,显然时间复杂度也是指数级别!

    二、分析在递归的过程中是否存在大量的重叠子问题(动态规划第二步)

    由上一节的递归树可知,存在重叠子问题,上一节中的 9, 8,都重复算了,所以存在重叠子问题!

    三、采用备忘录的方式来存子问题的解以避免大量的重复计算(剪枝)

    既然我们知道存在重叠子问题,那么就可以用备忘录来存储中间结果达到剪枝的目的

    publicclass Solution {
    
        // 保存中间结果
        privatestatic HashMap<Integer, Integer> map = new HashMap();
    
        // 带备忘录的递归求解
        private static int exchangeRecursive(int amount, int[] coins) {
            if (map.get(amount) != null) {
                return map.get(amount);
            }
            // 说明零钱已经凑完
            if (amount == 0) {
                return0;
            }
    
            // 说明没有满足的条件
            if (amount < 0) {
                return -1;
            }
    
            int result = Integer.MAX_VALUE;
            for (int i = 0; i < coins.length; i++) {
                int subMin = exchangeRecursive(amount - coins[i], coins);
                if (subMin == -1) continue;
                result = Math.min(subMin + 1, result);
            }
    
            // 说明没有符合问题的解
            if (result == Integer.MAX_VALUE) {
                return -1;
            }
    
            map.put(amount, result);
            return result;
        }
    
        public static  void main(String[] args)  throws Throwable {
            int amount = 11;
            int[] coins = {1,2,5};
            int result = exchangeRecursive(amount, coins);
            System.out.println("result = " + result);
        }
    }
    

    四、改用自底向上的方式来递推,即动态规划

    前面我们推导出了如下递归公式

    f(amount, coins) = min{ f(amount - coins[i]) + 1) }, 其中 i 的取值为 0 到 coins 的大小,coins[i] 表示选择了此硬币, 1 表示选择了coins[i]  这一枚硬币
    

    从以上的递推公式中我们可以获取 DP 的解题思路,我们定义 DP(i) 为凑够零钱 i 需要的最小值,状态转移方程如下

    DP[i] =  min{ DP[ i - coins[j] ] + 1 } = min{ DP[ i - coins[j] ]} + 1,  其中 j 的取值为 0 到 coins 的大小,i 代表取了 coins[j] 这一枚硬币。
    

    于是我们只要自底向上根据以上状态转移方程依次求解 DP[1], DP[2],DP[3].,…DP[11],最终的 DP[11],即为我们所求的解

    // 动态规划求解
    private static int exchangeDP(int amount, int[] coins) {
        int[] dp = newint[amount + 1];
        // 初始化每个值为 amount+1,这样当最终求得的 dp[amount] 为 amount+1 时,说明问题无解
        for (int i = 0; i < amount + 1; i++) {
            dp[i] = amount + 1;
        }
    
        // 0 硬币本来就没有,所以设置成 0
        dp[0] = 0;
    
        for (int i = 0; i < amount + 1; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j]) {
                    dp[i] = Math.min(dp[i- coins[j]], dp[i]) + 1;
                }
            }
        }
    
        if (dp[amount] == amount + 1) {
            return -1;
        }
        return dp[amount];
    }
    

    画外音:以上只是求出了凑成零钱的的最小数量,但如果想求由哪些面值的硬币构成的,该如何修改呢?

    凑零钱这道题还可以用另外一道经典的青蛙跳台阶的思路来考虑,从最底部最少跳多少步可以跳到第 11 阶,一次可以跳 1,2,5步 。由此可知最后一步一定是跳 1 或 2 或 5 步,于是如果用 f(n) 代表跳台阶 n 的最小跳数,则问题转化为了求 f(n-1),f(n-2) ,f(n-5)的最小值。
    在这里插入图片描述
    如图示:最后一跳一定是跳 1 或 2 或 5 步,只要求 f(n-1),f(n-2) ,f(n-5)的最小值即可

    写出递推表达式, 即:

     f(n) = min{ f(n-1)f(n-2)f(n-5)} + 11代表最后一跳)
    

    我们的 DP 状态转移方程对比一下,可以发现两者其实是等价的,只不过这种跳台阶的方式可能更容易理解。

    总结

    本文通过几个简单的例子强化了大家动态规划的三要素:最优子结构,状态转移方程,重叠子问题的理解,相信大家对动态规划的理解应该深刻了许多,怎么看出是否可以用动态规划来解呢,先看题目是否可以用递归来推导,在用递归推导的过程如果发现有大量地重叠子问题,则有两种方式可以优化,一种是递归+ 备忘录,另一种就是采用动态规划了,动态规划一般是自下而上的, 通过状态转移方程自下而上的得出每个子问题的最优解(即最优子结构),最优子结构其实也是穷举了所有的情况得出的最优解,得出每个子问题的最优解后,也就是每个最优解其实是这个子问题的全局最优解,这样依赖于它的上层问题根据状态转移方程自然而然地得出了全局最优解。动态规划自下而上的求解方式还有一个好处就是避免了重叠子问题,因为依赖于子问题的上层问题可能有很多,如果采用自顶而下的方式来求解,就有可能造成大量的重叠子问题,时间复杂度会急剧上升。

    展开全文
  • 动态规划算法思想解决找零钱问题

    万次阅读 2017-10-16 14:20:54
    前言  关于找零钱问题,网上已经有很多相关的资料以及优秀的文章博客等。这里写这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受起来更易理解点;... 动态规划(dynamic progr...
  • 1)动态规划算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。 2)动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题...
  • (2)动态规划算法与分治算法类似,其基本思想也是将待求问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解 (3)与分治算法不同的是,适合于动态规划求解的问题,经分解得到子问题往往不是相互独立...
  • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立...
  • 首先我们要清楚java共有五大算法,分别是分治算法,回溯...那么动态规划算法到底是什么思维来解决问题的呢?首先动态规划算法基本概念要清楚认识。 1.动态规划的基本概念: 动态规划过程是:每次决策依赖于当前状...
  • 算法-动态规划算法(详解)

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

    千次阅读 多人点赞 2019-07-29 09:47:07
    动态规划算法似乎是一种很高深莫测的算法,你会在一些面试或算法书籍的高级技巧部分看到相关内容,什么状态转移方程,重叠子问题,最优子结构等高大上的词汇也可能让你望而却步。 而且,当你去看用动态规划解决某个...
  • 整篇文章分析整个动态规划算法,什么是动态规划,及动态规划算法在字符串匹配中使用、分治法的差别点、动态规划优点;
  • 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 什么是动态规划 动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题...
  • 首先,本博客为原创作品,欢迎指导,随意转载,如果可以请转载时说明出处,附上...动态规划算法基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题...
  • 五大常用算法(二) - 动态规划算法

    千次阅读 2018-10-16 16:49:12
    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相...
  • 陈甜甜【摘要】介绍了动态规划基本理论,包括动态规划基本概念和基本原理,并针对生产与存储问题进行了分析,然后结合Matlab做了编程处理,使复杂问题简单化,从而使问题能更方便地得到解决。【关键词】动态规划...
  • 基于01背包问题的动态规划算法

    千次阅读 2020-08-12 00:31:59
    动态规划中的最优决策表 最终版动态规划 总结 初步认识动态规划 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 我们可以简单地将动态规划与贪心算法...
  • 掌握动态规划方法贪心算法思想 掌握最优子结构原理 了解动态规划一般问题 二、实验内容 编写一个简单的程序,解决0-1背包问题。设N=5,C=10,w={2,2,6,5,4},v={6,3,5,4,6} 合唱队形安排问题 【问题描述】N位...
  • 动态规划——十大算法

    千次阅读 2020-03-29 23:45:52
    2、动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 3、与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往...
  • 动态规划及贪心算法

    千次阅读 2020-02-22 08:39:47
    动态规划(Dynamic programming,简称DP);核心思想是把原问题分解成子问题进行求解,也就是分治的思想。 那么什么问题适合用动态规划呢?我们通过一个现实中的例子,来理解这个问题。大家可能在公司里面都有一定的...
  • 算法分析与设计实验报告——0-1背包问题的动态规划算法实现 目录:算法分析与设计实验报告——0-1背包问题的动态规划算法实现一、 实验目的二...用c++语言实现用动态规划算法解决0-1背包问题,分析时间复杂性,体会动态
  • 什么是动态规划算法

    千次阅读 2020-12-20 21:25:51
    定义 动态规划是运筹学的一个分支,是求解决策过程的最优化的过程。...动态规划算法常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应一个值,我们希望找到具有最优值的解,动态
  • 动态规划算法介绍

    千次阅读 2019-02-17 19:34:49
    动态规划算法的思想和分治算法类似,基本思想也是将待求问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。因此,动态规划算法是自底向上进行计算的,每一个子问题可以看成是一个状态,...
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...
  • 动态规划算法通常用于求解具有某种最优解的问题 基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,动态规划分解得到的子问题往往不是互相独立的...
  • 动态规划算法基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过...
  • 动态规划算法基本原理

    千次阅读 2013-11-28 23:09:47
    动态规划一般也只能应用于有最...动态规划算法分以下4个步骤: 1.描述最优解的结构 2.递归定义最优解的值 3.按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础。 4.由计算出的结果构造一个最优解。 

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,198
精华内容 16,479
关键字:

动态规划算法的基本解决思路