精华内容
下载资源
问答
  • 动态规划算法求解的前提
    千次阅读
    2021-11-01 11:11:35

    1、动态规划的定义

    动态规划算法:多阶段决策过程,每步求解的问题是后面阶段求解问题的子问题,每步决策将依赖于以前步骤的决策结果;


    2、使用动态规划技术的必要条件:满足优化原则

    优化原则: 一个最优决策序列的任何子序列本身一定的是相对于子序列的初始和结束状态的最优决策序列;

    最优解不满足优化原则的问题不能使用动态规划算法;


    3、动态规划算法的要素

    1. 划分子问题,确定子问题边界,将问题求解转变成多步判断的过程;
    2. 定义优化函数,以该函数极大(或极小)值作为依据,确定是否满足优化原则;
    3. 列优化函数的递推方程和边界条件;
    4. 自底向上计算,设计备忘录(记录每一次计算的值);
    5. 考虑是否需要设立 标记函数(记录每个子问题的解);
    6. 用递归方程或备忘录估计时间复杂度;



    见《算法分析与设计》第2版 - 屈婉玲;
    见 配套视频教程:https://www.bilibili.com/video/BV1Ls411W7PB

    更多相关内容
  • 文章目录1.序2.动态规划的基本概念[^1]3.动态规划算法的基本思想[^2]4....这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。...

    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]引用自老师的课件

    展开全文
  • 动态规划

    1.基本思想

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

    2.解题步骤

    1. 找出最优解,并刻划其子结构的性质;
    2. 递归地定义最优值;
    3. 以自底向上的方式计算最优值
    4. 根据计算最优值时得到的信息,构造最优解

    3.基本要素

    最优子结构:原问题最优解包含其子问题的最优解。
    最优子结构是问题能用动态规划算法求解的前提。

    4.动态规划算法的理解

    每步求解的问题是后 面阶段求解问题的子问题. 每步决策将依赖于以前步骤的决策结果.

    5.动态规划与分治算法的异同

    治法与动态规划
    共同点 :⼆者都要求原问题具有最优⼦结构性质,都是将原问题分⽽治之,分解成若⼲个规模较⼩(⼩到很容易解决的程序)的⼦问题.然后将⼦问题的解合并,形成原问题的解.
    不同点:分治法将分解后的⼦问题看成相互独⽴的,通过⽤递归来做。
    动态规划将分解后的⼦问题理解为相互间有联系,有重叠部分,需要记忆,通常⽤迭代来做。
    链接:参考

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

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

    6.应用

    矩阵链相乘;最长公共子序列
    在这里插入图片描述

    展开全文
  • 一.动态规划算法的基本要素[^2] 最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优...最优子结构是问题能用动态规划算法求解前提。 注意:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的

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

    1. 最优子结构
      矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
      在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。
      利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
      注意:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)

    2. 重叠子问题
      递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
      动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。
      通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。
      动态规划算法是从暴力搜索算法优化过来的,如果我们不清楚暴力搜索的过程,就难以理解动态规划的实现,当我们了解了动态规划算法的基本原理的文字概述,实现条件之后,这时可能并不是太理解这种思想,去面对实际问题的时候也是无从下手,这个时候我们不能停留在文字层面上,而应该去学习经典动态规划算法的实现,然后倒回来看这些概念,便会恍然大悟。

    动态规划算法的难点在于 从实际问题中抽象出动态规划表dp,dp一般是一个数组,可能是一维的也可能是二维的,也可能是其他的数据结构。

    二.动态规划的关键点:

    1、最优化原理,也就是最有子结构性质。这指的是一个最优化策略具有这样的性质,无论过去状态和决策如何,对前面的决策所形成的状态而言,余下的决策必须构成最优策略,简单来说就是一个最优化策略的子策略总是最优的,如果一个问题满足最优化原理,就称其有最优子结构性质。

    2、无后效性,指的是某个状态下的决策的收益,只与状态和决策相关,与达到该状态的方式无关。

    3、子问题的重叠性,动态规划将原来指数级的暴力搜索算法改进到了具有多项式时间复杂度的算法,其中的关键在于解决了荣誉,重复计算的问题,这是动态规划算法的根本目的。

    4、总体来说,动态规划算法就是一系列以空间换取时间的算法。

    三. 例题

    例1:最大m子段和问题

    描述:给定N(1 <= N <= 100000)个绝对值不超过32768的整数( 可能为负数)组成的序列a[1],a[2],a[3],…,a[N],求从该序列中取出M个连续不相交子段,使这M个子段的和最大。如果子段全都是负数则最大子段和也为负数。

    输入:有一个正整数M和一个正整数N,后面紧跟N个绝对值不大于32768的整数

    输出:最大M子段和

    样例输入:

    8 2 6 -1 4 -2 3 -2 3

    样例输出:
    8

    最大m子段和问题

    令dp[i][j]表示在前i个数中选取j段且第i个数在最后一组中的最大子段和

    那么现在对于第i个数有两种决策

    第i个数和第i-1个数连接成一段

    dp[j][i]= dp[i-1][j] + a[i];

    第i个数自己单独做一段.那么前面就需要有j-1段

    dp[i][j] = max{dp[k][j-1]<|j-1<=k<i}+a[i];

    就有了状态转移方程

    dp[i][j]=max(dp[i-1][j],
    max{dp[k][j-1]|j - 1<= k < i})+a[i];

    代码如下:
    const int N= 10005, INF= 1e9;
    int a[N], dp[N][N];
    int main()
    {
    int n, m;
    while(~scanf("%d%d", &m, &n))
    {
    for(int i=1;i<=n; i++)
    scanf("%d", &a[i]);
    memset(dp, 0, sizeof (dp));
    int ans = -INF;
    for(int j=1;j<=m; j++)
    {
    for(int i=j;i<=n; i++)
    {
    dp[i][j]=i-1<j?-INF:dp[i-1][j];
    for(int k=j-1 ;k<i;++k)
    dp[i][j]=max(dp[i][j],dp[k][j-1]);
    dp[i][j]+=a[i];
    if(j == m) ans=max(ans,dp[i][j]);
    }
    }
    printf("%d\n", ans);
    }
    return 0;
    }

    例2.线段覆盖

    数轴上有n条线段,线段的两端都是整数坐标,坐标范围在0~ 1000000,每条线段有一个价值,请从n条线段中挑出若干条线段,使得这些线段两两不覆盖(端点可以重合)且线段价值之和最大。n<=1000

    输入描述Input Description

    第一行一个整数n,表示有多少条线段。

    接下来n行每行三个整数, ai bi ci,分别代表第i条线段的左端点ai,右端点bi (保证左端点<右端点)和价值ci。

    输出描述Output Description

    输出能够获得的最大价值

    样例输入Sample Input

    3
    1 2 1

    2 3 2

    1 3 4

    样例输出Sample Output
    4

    按照右区间坐标排个序再来DP,DP[i]=max{DP[j], 1<=j<i}+第i条线段的价值。
    代码如下:
    #define get(x) scanf("%d", &x)

    #define put(x) printf("%d", x)

    #define cIs(x) memset(x, 0, sizeof(x))
    using namespace std;

    int n, res;
    int dp[1010];
    struct L
    {
    int I,r,c;
    }a[1010];
    bool cmp(L a, L b)
    {
    return a.r < b.r;
    }
    int main()
    {
    get(n);
    {
    for (int i=1;i<=n; i++)
    {
    get(a[i].I), get(a[i].r), get(a[i].c);
    }
    sort(a+1, a+n+1, cmp);
    cls(dp);
    for (int i=1;i<=n; i++)
    {
    int maxx= 0;
    for (int j=1;j<i;j++)
    if (a[i].I >= a[j].r)
    maxx = max(maxx, dp[j]);
    dp[i] = maxx + a[i].c;
    res = max(res, dp[i]);
    }
    put(res);
    return 0;
    }

    展开全文
  • 分治算法介绍: 分治算法是一种很重要的算法,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或...2)动态规划算法与分治算法类似,其基本思想也是先将待求解问题分解成若干个子问题,先求解子问题,然后
  • 矩阵连乘——动态规划算法

    千次阅读 多人点赞 2019-07-25 11:26:21
    矩阵连乘——动态规划算法 目录 矩阵连乘——动态规划算法 预备知识 前言 问题 应用动态规划方法的步骤 按照步骤分析问题 步骤1:最有括号化方案的结构特征 步骤2:一个递归求解方案 步骤3:计算最优代价 ...
  • 找零问题之动态规划求解 递归是从后往前逐步判断求解,17元有哪个和哪个组成,而哪个又由–和--组成,其实除了递归求解,也可以换种思路,从前往后逐步递推。 从小到大都求出来最优解,逐步递推。而大的最优解一定...
  • 分治算法,动态规划算法和贪心算法的区别和联系 (一)分治算法 分治算法为什么叫分治算法? 分治这个名字可以分成两部: 第一部分是分,表示把一个原问题分解成很多个小问题,逐个解决; 第二部分是治, 表示把得到的子问题...
  • 软件与算法设计训练 第一大题 1.某工厂计划要采购n台设备,每台设备的采购价格为pi(i=1,2…,n),工厂装备该设备后能产生的效益为vi(i=1,2,…n)。因为新冠疫情影响,该工厂大幅缩减了预算,用于本次采购的预算总金额...
  • 2019 NCTCS2019全国理论计算机科学学术年会 ( )求解矩形切割问题快速启发式-动态规划算法*尹爱华, 黄江海+, 胡冬萍, 陈冲江西财经大学 软件与物联网工程学院, 南昌 330013+ 通讯作者 E-mail: 1982589849@,硕士生摘 ...
  • 动态规划算法

    2021-05-31 10:16:57
    2 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 3 与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往...
  • 动态规划及贪心算法

    千次阅读 2020-02-22 08:39:47
    动态规划(Dynamic programming,简称DP);核心思想是把原问题分解成子问题进行求解,也就是分治的思想。 那么什么问题适合用动态规划呢?我们通过一个现实中的例子,来理解这个问题。大家可能在公司里面都有一定的...
  • 1 一个问题:换零钱方式的统计 SICP 第一章 1.2.2 树形递归中,有这么一问题:给了半美元,四分之一美元,10美分,5美分和1美分的...动态规划(Dynamic programming,DP),是研究一类最优化问题的方法,通过把原问...
  • 分治算法和动态规划算法都是通过对问题进行分解,通过对子问题的求解然后进行解重构,从而实现对原问题的求解。请指出这两种算法在对问题进行分解时各自所遵循的原则。 答:分治算法对问题进行分解时所遵循的原则...
  • 我们关注适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构和子问题重叠。我们还会再次讨论备忘方法,更深入地讨论在自顶向下方法中如何借助备忘机制来充分利用子问题重叠特性。 最优子结构 用...
  • 1 贪心自顶向下求解动态规划自底向上求解; 2 贪心最优解一定包含上一步的最优解,动态规划最优解不一定包含上一步的最优解; 3 贪心不能保证全局最优,动态规划(本质是穷举法)能保证全局最优; 4 贪心复杂度较...
  • 问题描述: 现有若干重量和价值各不相同的物品以及1个固定容量的背包,可以任意选择多个物品放入背包,如何让背包里装入的物品总价值最大?...2)解除注释,观察动态规划算法中填表详情。 温馨提示 关...
  • 目录动态规划简介设计动态规划算法的步骤动态规划原理 (Elements of dynamic programming)最优子结构 (Optimal substructure)重叠子问题 (Overlapping subproblems)重构最优解 (Reconstructing an optimal solution)...
  • 动态规划算法解01背包问题(思路及算法实现)

    万次阅读 多人点赞 2019-05-13 21:43:40
    动态规划算法动态规划就是一个填表的过程。该表记录了已解决的子问题的答案。求解下一个子问题时会用到上一个子问题的答案。{比如01背包问题:假如有1个背包,背包容量是10,有5个物品,编号为1,2,3,4,5,...
  • 动态规划算法初识

    2019-08-11 19:16:56
    接下来主要围绕动态规划来说说,去解释动态规划算法的内在。。。。 简述 动态规划求解出最优策略的原理是因为显著的降低了时间复杂度,提高了代码的运行效率,但动态规划确实是有点难学,不过一旦了解了解决思...
  • 分治算法 一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题...
  • C++ 吃透动态规划算法

    千次阅读 多人点赞 2021-08-14 19:14:37
    本文需要花费半天乃至一天的时间来学习, 前提内功深厚, 不然一时半会还真看不懂 觉得有用给个三连呗 !!! 文章目录 1. 介绍 2. 子序列问题 1143.最长公共子序列 300.最长递增子序列 2.1 最长递增子序列应用 354....
  • 基本认识 动态规划( dynamic ...动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它...
  • 动态规划解决最短路径问题

    万次阅读 多人点赞 2020-08-15 16:00:30
    最短路径问题(Shortest path problem):再不回退的前提下,找到A到F的最短路径 3.6.2 算法思路 A到B1的最短路径为4,前序节点为A; A到B2的最短路径为5,前序节点为A; A到C1的最短路径,我们可以看出,只有B1可以...
  • 动态规划、贪心算法、分治算法的优缺点分析

    万次阅读 多人点赞 2019-09-15 07:11:51
    3. 由于动态规划方法反映了动态过程演变的联系和特征,在计算时可以利用实际知识和经验提高求解效率。动态规划模型的缺点: 1. 没有统一的标准模型; 2. 数值方法求解时存在维数灾。(需要额外的内存空间,并且一维...
  • 当我堆算法题的概念还停留在1000题的时候,今天打开力扣一看,已经更新到1900道题了。真的是,没有进步就是在退步。 意识到了算法的重要性,也想通过算法来给自己提升一点自信,又或者说给自己增加一点底气! ...
  • 目录数据结构与算法系列数据结构与算法之哈希表数据结构与算法之跳跃表数据结构与算法之字典树数据结构与算法之平衡二叉树数据结构与算法之十大经典排序数据结构与算法之二分查找三模板数据结构与算法动态规划动态...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,888
精华内容 3,555
热门标签
关键字:

动态规划算法求解的前提