精华内容
下载资源
问答
  • 常见动态路由协议

    万次阅读 2018-06-08 20:06:52
    动态路由协议自己的路由算法,能够自动适应网络拓扑的变化,适用于具有一定数量三层设备的网络。缺点是配置对用户要求比较高,对系统的要求高于静态路由,并将占用一定的网络资源。 常见动态路...

    路由器要转发数据必须先配置路由数据,通常根据网络规模的大小可设置静态路由或设置动态路由。静态路由配置方便,对系统要求低,适用于拓扑结构简单并且稳定的小型网络。缺点是不能自动适应网络拓扑的变化,需要人工干预。动态路由协议有自己的路由算法,能够自动适应网络拓扑的变化,适用于具有一定数量三层设备的网络。缺点是配置对用户要求比较高,对系统的要求高于静态路由,并将占用一定的网络资源。

          常见的动态路由协议包括RIP、OSPF、IS-IS、IGRP、EIGRP、BGP等。RIP、OSPF、IS-IS、IGRP、EIGRP是内部网关协议(IGP),适用于单个ISP的统一路由协议的运行,一般由一个ISP运营的网络位于一个AS(自治系统)内,有统一的AS number(自治系统号)。BGP是自治系统间的路由协议,是一种外部网关协议,多用于INTERNET上,在不同运营商之间交换路由信息,在某些大型的企业的内部网络里,有时也会用到BGP路由协议。下面为大家介绍各种路由协议的特性。

     

    一、RIP路由协议
          RIP是Routing Information Protocol(路由信息协议)的简称。它是一种较为简单的内部网关协议IGP(Interior Gateway Protocol),主要用于规模较小的网络中,比如校园网以及结构较简单的地区性网络。对于更为复杂的环境和大型网络,一般不使用RIP。

          RIP是一种基于距离矢量(Distance-Vector)算法的协议,它通过UDP报文进行路由信息的交换,使用的端口号为520。

          RIP使用跳数(Hop Count)来衡量到达目的地址的距离,称为度量值。在RIP中,缺省情况下,路由器到与它直接相连网络的跳数为0,通过一个路由器可达的网络的跳数为1,其余依此类推。也就是说,度量值等于从本网络到达目的网络间的路由器数量。为限制收敛时间,RIP规定度量值取0~15之间的整数,大于或等于16的跳数被定义为无穷大,即目的网络或主机不可达。由于这个限制,使得RIP不可能在大型网络中得到应用。

          为提高性能,防止产生路由循环,RIP支持水平分割(Split Horizon)和毒性反转(Poison Reverse)功能。

          由于RIP的实现较为简单,在配置和维护管理方面也远比OSPF和IS-IS容易,因此在实际组网中仍有广泛的应用。

        RIP有两个版本:RIP V1和RIP V2。

        1、RIP V1是有类别路由协议(Classful Routing Protocol),它只支持以广播方式发布协议报文。RIP-1的协议报文中没有携带掩码信息,它只能识别A、B、C类这样的自然网段的路由,因此RIP-1无法支持路由聚合,也不支持不连续子网(Discontiguous Subnet)。

        2、RIP V2是一种无分类路由协议(Classless Routing Protocol),与RIP-1相比,它有以下优势:

        1)支持外部路由标记(Route Tag),可以在路由策略中根据Tag对路由进行灵活的控制。

        2)报文中携带掩码信息,支持路由聚合和CIDR(Classless Inter-Domain Routing)。

        3)支持指定下一跳,在广播网上可以选择到最优下一跳地址。

        4)支持使用组播方式发送更新报文,只有RIP-2路由器才能收到协议报文,减少资源消耗。

        5)支持对协议报文进行验证,并提供明文验证和MD5验证两种方式,增强安全性。


    二、OSPF路由协议
          OSPF(Open Shortest Path First)是IETF组织开发的一个基于链路状态的内部网关协议。目前针对IPv4协议使用的是OSPF Version 2(RFC2328);针对IPv6协议使用OSPF Version 3(RFC2740)。

     

    OSPF的特性如下:

    1、适应范围广:支持大规模网络,最多可支持几百台路由器。

    2、支持掩码:由于OSPF报文中携带掩码信息,所以OSPF协议不受自然掩码的限制,对VLSM提供很好的支持。

    3、快速收敛:在网络的拓扑结构发生变化后立即发送更新报文,使这一变化在自治系统中同步。

    4、无自环:由于OSPF根据收集到的链路状态用最短路径树算法计算路由,从算法本身保证了不会生成自环路由。

    5、区域划分:允许自治系统的网络被划分成区域来管理,区域间传送的路由信息被进一步抽象,从而减少了占用的网络带宽。

    6、等价路由:支持到同一目的地址的多条等价路由。

    7、路由分级:使用4类不同的路由,按优先顺序来说分别是:区域内路由、区域间路由、第一类外部路由、第二类外部路由。

    8、支持验证:支持基于区域和接口的报文验证,以保证报文交互的安全性。

    9、组播发送:在某些类型的链路上以组播地址发送协议报文,减少对其他设备的干扰。


    三、IS-IS路由协议
          IS-IS(Intermediate System-to-Intermediate System,中间系统到中间系统)最初是国际标准化组织ISO(the International Organization for Standardization)为它的无连接网络协议CLNP(ConnectionLess Network Protocol)设计的一种动态路由协议。

          为了提供对IP的路由支持,IETF在RFC1195中对IS-IS进行了扩充和修改,使它能够同时应用在TCP/IP和OSI环境中,称为集成化IS-IS(Integrated IS-IS或Dual IS-IS)。

          IS-IS属于内部网关协议IGP(Interior Gateway Protocol),用于自治系统内部。IS-IS是一种链路状态协议,使用最短路径优先SPF(Shortest Path First)算法进行路由计算,与OSPF协议有很多相似之处。

     

    四、IGRP路由协议
           IGRP协议是“内部网关路由协议(Interior Gateway Routing Protool)”的缩写,由Cisco于二十世纪八十年代独立开发,属于Cisco私有协议。IGRP和RIP一样,同属距离矢量路由协议,因此在诸多方面有着相似点,如IGRP也是周期性的广播路由表,也存在最大跳数(默认为100跳,达到或超过100跳则认为目标网络不可达)。IGRP最大的特点是使用了混合度量值,同时考虑了链路的带宽、延迟、负载、MTU、可靠性5个方面来计算路由的度量值,而不像其他IGP协议单纯的考虑某一个方面来计算度量值。目前IGRP已经被Cisco独立开发的EIGRP协议所取代,版本号为12.3及其以上的Cisco IOS(Internetwork Operating System)已经不支持该协议,现在已经罕有运行IGRP协议的网络。

     

    五、EIGRP路由协议
           EIGRP由于IGRP协议的种种缺陷以及不足,Cisco开发了EIGRP协议(增强型内部网关路由协议)来取代IGRP协议。EIGRP属于高级距离矢量路由协议(又称混合型路由协议),继承了IGRP的混合度量值,最大特点在于引入了非等价负载均衡技术,并拥有极快的收敛速度。EIGRP协议在Cisco设备网络环境中广泛部署。

     

    六、BGP路由协议
        
           BGP是“边界网关协议(Border Gateway Protocol)”的缩写,处理各ISP之间的路由传递。BGP是一种外部网关协议(EGP),与OSPF、RIP等内部网关协议(IGP)不同,其着眼点不在于发现和计算路由,而在于控制路由的传播和选择最佳路由。BGP协议具有如下特点:

    1、BGP使用TCP作为其传输层协议(监听端口号为179),提高了协议的可靠性。

    2、BGP进行域间的路由选择,对协议的稳定性要求非常高。因此用TCP协议的高可靠性来保证BGP协议的稳定性。

    3、BGP的对等体之间必须逻辑上连通,并进行TCP连接。目的端口号为179,本地端口号任意。

    4、BGP支持无类别域间路由CIDR。

    5、路由更新时,BGP只发送更新的路由,大大减少了BGP传播路由所占用的带宽,适用于在Internet上传播大量的路由信息。

    6、BGP是一种距离矢量路由协议,从设计上避免了环路的发生。

    7、AS之间:BGP通过携带AS路径信息标记途经的AS,带有本地AS号的路由将被丢弃,从而避免了域间产生环路。

    8、AS内部:BGP在AS内学到的路由不会在AS中转发,避免了AS内产生环路。

    9、BGP提供了丰富的路由策略,能够对路由实现灵活的过滤和选择。

    10、BGP提供了防止路由振荡的机制,有效提高了Internet网络的稳定性。

    11、BGP易于扩展,能够适应网络新的发展。

    展开全文
  • 常见动态规划问题总结

    千次阅读 2017-04-12 19:35:34
    于是决定将我见到的各类常见动态规划问题做个总结,方便后期复习。 动态规划即Dynamic Programming,简称DP,初接触动态规划问题会觉得这类问题很抽象,晦涩难懂,不同的问题的求解思路也是千差万别,但是从本质...

    最近毕业面临找工作的问题,在刷各大厂笔试题的时候发现大厂特别爱考一类问题,就是动态规划问题。于是决定将我见到的各类常见的动态规划问题做个总结,方便后期复习。
    动态规划即Dynamic Programming,简称DP,初接触动态规划问题会觉得这类问题很抽象,晦涩难懂,不同的问题的求解思路也是千差万别,但是从本质上来看动态规划问题,最核心的思想就是将一个大的问题拆分成一个一个的子问题,通过定义问题与子问题之间的状态转移关系,从而使得问题可以递推的解决下去。(绝大部分递归的问题都可以用动态规划的方式来解决,而且可以大大减小时间复杂度和空间复杂度)

    最长递增子序列(来自牛客网)

    对于一个数字序列,请设计一个复杂度为O(nlogn)的算法,返回该序列的最长上升子序列的长度,这里的子序列定义为这样一个序列U1,U2…,其中Ui < Ui+1,且A[Ui] < A[Ui+1]。
    给定一个数字序列A及序列的长度n,请返回最长上升子序列的长度。
    测试样例:
    [2,1,4,3,1,5,6],7
    返回:4

    这里用dp[i]表示以标识为i的元素为递增序列结尾元素的最长递增子序列的长度,由于这里的递增序列不要求严格相邻,因此A[i]需要和每一个A[j] (i>j)比较,如果存在A[i]>A[j],说明第i个元素可以接在第j个元素后面作为新的递增序列的结尾,因此dp[i] = max(dp[j]) + 1;否则,说明第i个元素比前面所有的数都小,以i元素作为结尾的d递增p序列长度为1,因此dp[i] = 1。最后只要取出dp中最大的值就是最长递增子序列的长度。将状态分析好了以后,问题就迎刃而解,这里附上手动撸的java版代码:

    public static int[] forward(List<Integer> list){
            int[] dp = new int[list.size()];
            dp[0] = 1;
    //max标记前面j个数中最大的子序列的长度
            int max;
            for(int i = 1; i < list.size();i++){
                max = 0;
                for(int j = 0; j < i; j++){
                    if(list.get(i) > list.get(j)){
                        max = max < dp[j] + 1 ? dp[j] + 1 : max;
                    }else{
                        max = max < 1 ? 1 : max;
                    }
                }
                dp[i] = max;
            }
            return dp;
        }

    最长公共子序列(来自牛客网)

    对于两个字符串,请设计一个高效算法,求他们的最长公共子序列的长度,这里的最长公共子序列定义为有两个序列U1,U2,U3…Un和V1,V2,V3…Vn,其中Ui&ltUi+1,Vi&ltVi+1。且A[Ui] == B[Vi]。
    给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。
    测试样例:
    “1A2C3D4B56”,10,”B1D23CA45B6A”,12
    返回:6

    我们用dp[i][j]来表示A串中的前i个字符与B串中的前j个字符的最长公共子序列长度,倘若A[i] = B[j],我们可以得到转移方程dp[i][j] = dp[i - 1][j - 1] + 1,如果A[i] != B[j],dp[i][j] = max(dp[i][j-1],dp[i-1][j])。

        public static int findLCS(String A, int n, String B, int m) {
            // write code here
            int[][] dp = new int[n + 1][m + 1];
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(A.charAt(i - 1) == B.charAt(j - 1)){
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }else{
                        dp[i][j] = Math.max(dp[i - 1][j - 1],Math.max(dp[i - 1][j],dp[i][j - 1]));
                    }
                }
            }
            return dp[n][m];
        }

    最长公共子串(来自牛客网)

    对于两个字符串,请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度),求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,…Vn,其中Ui + 1 == Ui+1,Vi + 1 == Vi+1,同时Ui == Vi。
    给定两个字符串A和B,同时给定两串的长度n和m。
    测试样例:
    “1AB2345CD”,9,”12345EF”,7
    返回:4

    这个问题与上面的问题类似,区别点在于这里是子串,是连续的,令dp[i][j]表示A串中的以第i - 1个字符与B串中的以第j - 1个字符结尾的最长公共子串的长度,但是仅当A[i-1] = B[j-1]且dp[i][j] = dp[i -1][j -1] + 1;A[i-1] != B[j-1]时,以他们结尾的公共子串长度必然为0;最后从dp中取出长度最大的值即为最长公共子串。

        public static int findLongest(String A, int n, String B, int m) {
            // write code here
            int[][] dp = new int[n + 1][m + 1];
            int max = 0;
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(A.charAt(i - 1) == B.charAt(j - 1)){
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }else{
                        dp[i][j] = 0;
                    }
                    if(max < dp[i][j]) max = dp[i][j];
                }
            }
            return max;
        }

    最小编辑代价问题(来自牛客网重点内容)
    对于两个字符串A和B,我们需要进行插入、删除和修改操作将A串变为B串,定义c0,c1,c2分别为三种操作的代价,请设计一个高效算法,求出将A串变为B串所需要的最少代价。
    给定两个字符串A和B,及它们的长度和三种操作代价,请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300,且三种代价值均小于等于100。
    测试样例:
    “abc”,3,”adc”,3,5,3,100
    返回:8

    这个问题相比前面的几个问题更加抽象一些,我们需要定义四种情况,首先令dp[i][j]表示将A串中的前i个字符转换成B串中的前j个字符所需要的代价,第一种是A[i] = B[j]时,我们不需要做任何操作可以进入下一字符的比较,状态转移方程为dp[i][j] = dp[i - 1][j - 1];第二种情况是删除A串中的最后一个字符,使得A串和B串相等,状态转移为dp[i][j] = dp[i-1][j] + c1 ;第三种是在B串中插入一个字符使得A串和B串相等,即B串中去掉最后一个字符与A现在的A串相等,转移方程为dp[i][j] = dp[i][j - 1] + c0;第四种是将A串中的一个字符修改从而使得A串和B串相等,即A串和B串最后一个字符不相等,其他位都相等,状态状态转移为dp[i][j] = dp[i-1][j-1] + 1。在后三种情况中,我们都可以将A字符串变为B字符串,但是我们这里要求的是最小代价,因此dp[i][j] = min(情况2,3,4)。
    java版本的代码如下:

        public static int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
            // write code here
            int[][] dp = new int[n+1][m+1];
            for(int i = 0; i <=n; i++) dp[i][0] = i*c0;
            for(int j = 0; j <=m; j++) dp[0][j] = j*c1;
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(A.charAt(i - 1) == B.charAt(j - 1)){
                        dp[i][j] = dp[i - 1][j - 1];
                    }else{
                        dp[i][j] = Math.min(dp[i - 1][j - 1] + c2,Math.min(dp[i][j - 1] + c0,dp[i - 1][j] + c1));
                    }
                }
            }
            return dp[n][m];
        }

    0/1背包问题
    0/1背包问题是动态规划问题中的经典问题
    问题描述:
    给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大??
    在选择物品的时候,对每种物品i只有两种选择,即装入背包或不装入背包。不能讲物品i装入多次,也不能只装入物品的一部分。因此,该问题被称为0-1背包问题。

    对于这个问题,我们定义最大价值为Max(N,C),这里我们可以分两种情况来考虑
    情况一:包中放了第N个物品
    那么我们现在还剩下N-1个物品,以及C-cn的背包容量,这种情况下我们得到的最大的价值为Max(N-1,C-cn) + N * vn,这即是上面问题的子问题
    情况二:包中没有放第N个物品
    那么我们还剩下N-1个物品以及C的背包容量,在这种情况下,我们得到的最大的价值为Max(N-1,C)
    由上面的分析我们可以定义dp[i][j]表示有i个物品和j的容量的情况下可以得到的最大的价值,很容易通过情况一二得到状态转移方程式如下:
    dp[i][j] = Max(dp[i-1][j-ci] + vi,dp[i-1][j])
    为了方便理解,这里给出一个具体的0/1背包实例

    王强今天很开心,公司发给N元的年终奖。王强决定把年终奖用于购物,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多,为了不超出预算,他把每件物品规定了一个重要度,分为 5 等:用整数 1 ~ 5 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格(都是 10 元的整数倍)。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
    设第 j 件物品的价格为 v[j] ,重要度为 w[j] ,共选中了 k 件物品,编号依次为 j 1 , j 2 ,……, j k ,则所求的总和为:
    v[j 1 ]w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。(其中 为乘号)
    这里直接给出java版本的源码

    import java.util.*;
    
    /**
     * Created by 梅晨 on 2017/3/26.
     */
    public class Main {
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
                String[] moneyAndNum = in.nextLine().split(" ");
                int money = Integer.valueOf(moneyAndNum[0]);
                int n = Integer.valueOf(moneyAndNum[1]);
                int[][] weight = new int[60][3];
                int[][] val = new int[60][3];
                int[][] dp = new int[n+1][money+1];
                int index = 1;
                for(int i = 0; i < n; i++){
                    String[] strs = in.nextLine().split(" ");
                    int p = Integer.valueOf(strs[0]);
                    int w = Integer.valueOf(strs[1]);
                    int q = Integer.valueOf(strs[2]);
                    if(q == 0){
                        weight[index][0] = p;
                        val[index][0] = w * p;
                        index++;
                    }else{
                        if(weight[index - 1][1] == 0){
                            weight[index - 1][1] = p;
                            val[index - 1][1] = w * p;
                        }else{
                            weight[index - 1][2] = p;
                            val[index - 1][2] = w * p;
                        }
                    }
                }
                for(int i = 1; i < n + 1; i++){
                    for(int j = 1; j < money + 1; j++){
                    //j空间够放第i个物品
                        if(weight[i][0] <= j){
                        //dp[i - 1][j]表示没有放第i个物品,dp[i - 1][j - weight[i][0]]表示放了第i个物品
                            dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weight[i][0]] + val[i][0]);
                        }
                        if(weight[i][0] + weight[i][1] <= j){
                            dp[i][j] = Math.max(dp[i][j],Math.max(dp[i - 1][j],dp[i - 1][j - weight[i][0] - weight[i][1]] + val[i][0] + val[i][1]));
                        }
                        if(weight[i][0] + weight[i][2] <= j){
                            dp[i][j] = Math.max(dp[i][j],Math.max(dp[i - 1][j],dp[i - 1][j - weight[i][0] - weight[i][2]] + val[i][0] + val[i][2]));
                        }
                        if(weight[i][0] + weight[i][1] + weight[i][2] <= j){
                            dp[i][j] = Math.max(dp[i][j],Math.max(dp[i - 1][j],dp[i - 1][j - weight[i][0] - weight[i][1] - weight[i][2]] + val[i][0] + val[i][1] + val[i][2]));
                        }
                    }
                }
                System.out.println(dp[n][money]);
            }
        }
    
    
    
    }
    
    

    股票收益最大化问题(来自leetcode)
    股票收益最大化问题1

    股票收益最大化问题2
    有一个数组,数组中的第i个数表示第i天股票的价格,现在要求设计一种算法,来取得最大化的股票收益,这里你可以进行尽可能多次的交易,但是交易不能交叉,即买股票之前必须先把上一只股票卖出。
    这里我们来分析状态转移的问题,在第i天,我们观察股票的价格,如果price[i] >price[i - 1],表明第i天相对第i-1天是有收益的,倘若我们第i天卖出股票,则相比第i-1天收益增加,方程式为dp[i] = dp[i-1] + price[i] - price[i-1],如果price[i]<=price[i-1],如果我们在第i天卖出股票,则是亏损,因此我们选在继续持有股票,即方程式为dp[i] = dp[i-1]。有的朋友可能会困惑,这里只有卖出操作,那怎么知道它什么时候买进股票呢,我们仔细的分析一下,可以发现在股票下跌的时候,是不进行任何操作的,也没有任何收益,只有在股票价格最低,并且开始上升的时候,我们开始买进,并且在股价最高的时候抛出。
    下面给出参考的java版本代码:

    public class Solution {
        public int maxProfit(int[] prices){
            int[] dp = new int[prices.length];
            if(prices.length == 0) return 0;
            dp[0] = 0;
            for(int i = 1; i < prices.length;i++){
                if(prices[i] > prices[i - 1]){
                    dp[i] = dp[i - 1] + prices[i] - prices[i - 1];
                }else{
                    dp[i] = dp[i - 1];
                }
            }
            return dp[prices.length - 1];
        }
    }
    
    **称砝码问题**

    现有一组砝码,重量互不相等,分别为m1,m2,m3…mn;
    每种砝码对应的数量为x1,x2,x3…xn。现在要用这些砝码去称物体的重量,问能称出多少中不同的重量。

    注:
    称重重量包括0
    输入描述:
    输入包含多组测试数据。

    对于每组测试数据:

    第一行:n — 砝码数(范围[1,10])

    第二行:m1 m2 m3 … mn — 每个砝码的重量(范围[1,2000])

    第三行:x1 x2 x3 …. xn — 每个砝码的数量(范围[1,6])

    这里的状态转移方程很容易得到,在可用砝码数量不为0的情况下,如果w-mi的重量可以称出来,则w的重量也可以称出来。基于这个状态转移方程,我们可以定义一个大小为总重量的数组,用于标记每个重量是否可以称出来,即maxWeight = mi * xi ( 0

    import java.util.Scanner;
    
    /**
     * Created by 梅晨 on 2017/4/23.
     */
    public class Main {
        public static void main(String[] args){
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                int n = in.nextInt();
                int[] m = new int[n];
                int[] x = new int[n];
                for(int i = 0; i < n;i++){
                    m[i] = in.nextInt();
                }
                for(int i = 0; i < n; i++){
                    x[i] = in.nextInt();
                }
                int max = 0;
                for(int i = 0; i < n;i++){
                    max += m[i] * x[i];
                }
                int[] dp = new int[max + 1];
                dp[0] = 1;
                for(int i = 0; i < n;i++){
                    for(int k = max; k >= 1;k--){
                        for(int j = x[i]; j >= 0;j--){
                            if((k-j * m[i] >= 0) && (dp[k-j * m[i]] == 1)){
                                dp[k] = 1;
                            }
                        }
                    }
                }
                int num = 0;
                for(int i = 0; i <= max; i++){
                    if(dp[i] == 1){
                        num++;
                    }
                }
                System.out.println(num);
            }
        }
    }
    
    展开全文
  • 动态规划常见类型总结

    千次阅读 多人点赞 2019-03-26 23:55:28
    严格来说,递推不属于动态规划问题,因为动态规划不仅递推过程,还要决策(即取最优),但广义的动态规划是可以包含递推的,递推是一类简单的、特殊的动态规划,毕竟动态规划与递推密不可分。动态规划类型主要...

    本文针对动态规划的常见类型进行总结。虽说总结的是动态规划,但顺便把递推也放了进来。严格来说,递推不属于动态规划问题,因为动态规划不仅有递推过程,还要有决策(即取最优),但广义的动态规划是可以包含递推的,递推是一类简单的、特殊的动态规划,毕竟动态规划与递推密不可分。动态规划类型主要分为纯粹动态规划问题和复合动态规划问题。

    几点说明:

    1、博主本人于2012年对信息学竞赛中的动态规划问题进行了总结,最初以名为《NOIP的DP总结之DP类型》的文档上传至百度文库(当然题目难度不限于NOIP,还包括NOI甚至IOI级别较难的题),时隔6年,决定将该总结以博客形式发表,并且原文内容不进行改动。

    2、本总结中,涉及不少题目及其解题报告的原版照抄,但部分题目无法查证原始出处,本着以分享的目的写入总结,若有不当之处,还请包涵;若实在不妥,可请指出,本人尽快纠正不当之处。

    3、总结中涉及的不少题目未加描述,读者可自行百度搜索题目名,建议搜索关键词加上“动态规划”或“DP”。

    4、总结中涉及的代码为Pascal语言,因总结之年代久远,烦请见谅;代码是相通的,理解代码的思路即可。

     

    目录

    一、资源型

    01背包

    完全背包

    多重背包

    二维费用背包

    分组背包

    有依赖的背包

    泛化物品

    背包问题的经典变形

    背包问题的搜索方法

    崔天翼大牛推荐的相关题目(USACO)

    其他

    二、线性动态规划

    三、区间动态规划(剖分问题)

    四、坐标动态规划(平面、地图)

    五、树型动态规划

    六、字符串动态规划

    七、贪心动态规划

    八、多进程动态规划

    九、状压动态规划

    十、判定型动态规划

    十一、目标型动态规划

    十二、概率动态规划

    十三、二次动态规划(双重动态规划)

    十四、递推问题

    十五、计数问题


     

    一、资源型

    主要是背包问题,背包部分的资料来源主要是《背包九讲》,另外也有自己的一些补充。 背包部分可以添加个叫“+-1背包”的家伙(属判定型动态规划);其次还有机器分配类问题。

    01背包

    这个是最基础的。

    首先要注意问法,是否必须完全装满,若是,则初值除f[i,0]=0外全赋值为负无穷。

    空间优化:二维变一维,注意枚举顺序要变为downto(倒序枚举)!

    时间优化:内层枚举的下界取 max{V-sum{w[i..n]},c[i]}

    相关题目:01背包母题,采药,poj2184,poj1882,poj1252,poj2063,poj1717poj1203

    变形:

    1 判定性01背包:

    装箱问题,石子归并(装half箱),补圣衣,挤牛奶,积木城堡

    2 多包限制顺序型01背包:

    USACO Raucous Rockers

    (多个背包,不可以重复放物品,但放物品的顺序有限制。)

    F[I,j,k]表示决策到第i个物品、第j个背包,此背包花费了k的空间。

    f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t]+p)

     

    完全背包

    空间优化:变为一维。注意顺序枚举。(对应于时间优化4)

    时间优化(前3个其实都用不上,只是了解下思想):

    1 若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。首先将费用大于V的物品去掉,然后使用类似计数排序的做法,计算出费用相同的物品中价值最高的是哪个,可以O(V+N)地完成这个优化。这个优化一般作用较小,非常必要时再用。

    2 转化的思想(此处未优化):将物品i拆成V/c[i]个。

    3 更高效的转化方法是:把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品,其中k满足c[i]*2^k<=V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品,是一个很大的改进。4  O(nv)的方法:将01背包的费用枚举由倒序改为顺序即可。

    (值得一提的是,上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。)

    题目:完全背包母题,hdu1114,soj3664,系统可靠性

     

    多重背包

    原始方程: f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

    复杂度是O(V*Σn[i])。

    优化:

    1 物品i拆分成num[i]个(复杂度不变)。

    2 二进制拆分,将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。转化为了复杂度为O(V*Σlog n[i])的01背包问题。可以证明正确性。

    证明:

    若x=2^k-1,用1,2,4……2^(k-1)进行01选取可以组合1到x之间的任意一个数;

    若x=2^k-1+y,(1<=y<2^k),用1,2,3……2^(k-1),y进行01选取可以组合1到x之间的任意一个数,为什么呢?

    对于2^k<=w<=x,有w=u+y,其中必有1<=u<=2^k-1,因此u可以通过01选取组合,从而w可以通过01选取组合。

    代码:
    procedure MultiplePack(cost,weight,amount)
        if cost*amount>=V
            CompletePack(cost,weight)
            return
        integer k=1
        while k<amount
            ZeroOnePack(k*cost,k*weight)
            amount=amount-k
            k=k*2
        ZeroOnePack(amount*cost,amount*weight)
    

    3 单调队列优化[O(nc)]

       对于第 i 种物品来说,已知体积 v,价值 w,数量 k,那么可以按照当

    前枚举的体积 j 对v的余数把整个动规数组分成 v份,以下是 v=3 的情况:

    我们可以把每一份分开处理,假设余数为 d。

    现在看到分组以后,编号 j 可以从 j-k 到 j-1 中的任意一个编号转移而来(因为相邻的体积正好相差 v) ,这看上去已经和区间最大值有点相似了。但是注意到由于体积不一样,显然体积大的价值也会大于等于体积小的,直接比较是没有意义的,所以还需要把价值修正到同一体积的基础上。比如都退化到 d,也就是说用 F[j*v+d]- j*w来代替原来的价值进入队列。

    代码:

    procedure insert(x,y:longint);//插入到一个价值单调递减,使用次数单调递增的队列中
     begin
      while (l<=r)and(b[r]<=y) do dec(r);
      inc(r);a[r]:=x;b[r]:=y;
     end;
    begin
     readln(n,m);  //n为物品个数、m为背包容量
     for i:=1 to n do
      begin
        read(v,w,c);  //读入当前物品:v为物品体积、w为物品价值、c为物品可用次数
        if m div v<c then c:=m div v;  //最多可使用次数
        for k:=0 to v-1 do  //把所有的体积按除以v的余数划分为0~v-1
         begin
           l:=1;r:=0;  //清空队列
           for j:=0 to (m-k) div v do  //余数为k的又分为k,v+k,2*v+k…j*v+k…
             begin
              insert(j,f[j*v+k]-j*w);  //等效于把体积统一到k,价值减去j*w,这样比较优劣才有意义
             while a[l]<j-c do inc(l);  //删除次数超过c的
              f[j*v+k]:=b[l]+j*w;      //用队列头的值更新f[j*v+k]
             end;
         end;
      end;
      writeln(f[m]);
    end.

    题目:砝码秤重,tyvj1086,zoj2156,poj2392,hdu1085

    poj1014,divide(见动态规划2)

     

    二维费用背包

    就是限制条件多了一个,变成了二维容量,从而状态多了一维而已。

    题目:hdu3236,打包(见动态规划set)poj2184

     

    分组背包

    有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

    这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值,则有: f[k][v] =max{ f[k-1][v],f[k-1][v-c[i]]+w[i] | 物品i属于组k }

    使用一维数组的伪代码如下:

    for 所有的组k
        for v=V..0
            for 所有的i属于组k
                f[v]=max{f[v],f[v-c[i]]+w[i]}

    注意这里的三层循环的顺序, “for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

    小优化:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。首先将费用大于V的物品去掉,然后使用类似计数排序的做法,计算出费用相同的物品中价值最高的是哪个,可以O(V+N)地完成这个优化。

    题目:hdu3033 ,hdu3449

     

    有依赖的背包

    简化的问题

    这种背包问题的物品间存在某种“依赖”的关系。也就是说,i依赖于j,表示若选物品i,则必须选物品j。为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的物品所依赖;另外,没有某件物品同时依赖多件物品

    这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法,将不依赖于别的物品的物品称为“主件”,依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。

    按照背包问题的一般思路,仅考虑一个主件和它的附件集合。可是,可用的策略非常多,包括:一个也不选,仅选择主件,选择主件后再选择一个附件,选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。(事实上,设有n个附件,则策略有2^n+1个,为指数级。)

    转化:考虑到所有这些策略都是互斥的(也就是说,你只能选择一种策略),所以一个主件和它的附件集合实际上对应于分组背包中的一个物品组,每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品,其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法,因为物品组中的物品还是像原问题的策略一样多。

    优化

    对于一个物品组中的物品,所有费用相同的物品只留一个价值最大的,不影响结果。所以,我们可以对主件i的“附件集合”先进行一次01背包,得到费用依次为0..V-c[i]所有这些值时相应的最大价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组,其中费用为c[i]+k的物品的价值为f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的,通过一次01背包后,将主件i转化为V-c[i]+1个物品的物品组,就可以直接应用分组背包的算法解决问题了。

    更一般的问题依赖关系以图论中“森林”的形式给出(森林即多叉树的集合),也就是说,主件的附件仍然可以具有自己的附件集合,限制只是每个物品最多只依赖于一个物品(只有一个主件)且不出现循环依赖。

    解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。事实上,这是一种树形动态规划,其特点是每个父节点都需要对它的各个儿子的属性进行一次动态规划以求得自己的相关属性。这已经触及到了“泛化物品”的思想。这个“依赖关系树”每一个子树都等价于一件泛化物品,求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。

    树形转链式

     

    题目:

    选课:有n^2做法。金明的预算方案

     

    泛化物品

    定义:考虑这样一种物品,它并没有固定的费用和价值,而是它的价值随着你分配给它的费用而变化。(详见背包九讲)

     

    背包问题的经典变形

    1 输出方案

    2 输出字典序最小的最优方案

    先逆序化,再普通动态规划。只是在输出方案时要注意,如果f[i][v]==f[i-1][i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同时成立,应该按照后者(即选择了物品i)来输出方案。

    3 求方案总数

    即装满背包或将背包装至某一指定容量的方案总数。

    对于这类改变问法的问题,一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品,转移方程即为 f[i][v] =sum{ f[i-1][v], f[i][v-c[i]] }

    初始条件f[0][0]=1。

    4 求最优方案总数

    这个较简单。

    5 求次优解、第 K 优解

    维护一个k优解的有序序列,合并采用归并法可达到O(k),故总复杂度为最优解问题的k倍。

     

    背包问题的搜索方法

    背包问题并不是所有的都可以动态规划,有些需要搜索!

    1 剪枝方法:最优性与可行性

    2 搜索顺序的选择:性价比法,体积大的放前面,随机化数据(以防出题人坑爹)

    3 子集和问题(以前lyp似乎出过):二分+hash。

    4 动态规划?搜索?

    在看到一道背包问题时,应该用搜索还是动态规划呢?

    首先,可以从数据范围中得到命题人意图的线索。如果一个背包问题可以用动态规划解,V一定不能很大,否则O(VN)的算法无法承受,而一般的搜索解法都是仅与N有关,与V无关的。所以,V很大时(例如上百万),命题人的意图就应该是考察搜索。另一方面,N较大时(例如上百),命题人的意图就很有可能是考察动态规划了。

    另外,当想不出合适的动态规划算法时,就只能用搜索了。例如看到一个从未见过的背包中物品的限制条件,无法想出动态规划的方程,只好写搜索以谋求一定的分数了。

     

    崔天翼大牛推荐的相关题目(USACO)

    • Inflate (+) (基本01背包)
    • Stamps (+)(!) (对初学者有一定挑战性)
    • Money
    • Nuggets
    • Subsets
    • Rockers (+) (另一类有趣的“二维”背包问题)
    • Milk4 (!) (很怪的背包问题问法,较难用纯动态规划求解)

     

    其他

    机器分配:简单的二维动态规划

    +-1背包

     

    二、线性动态规划

    何谓线性动态规划?有人认为是按时间复杂度来定义:复杂度由n惟一确定,且不能继续优化的动态规划为线性动态规划。我这里不做严格定义(也没找到理论的严格定义)。暂且理解为其动态规划的结构为线型的、链式的,区别于地图型(坐标型),树型,图型等。也可理解为可以从头到尾(或从尾到头)按数据列的生成顺序动态规划的一类动态规划问题。因此狭义地讲,区间动态规划也不属于线形的。

    典型题目:

    叠放箱子(?见动态规划2)、买车票、文字游戏、最佳加法表达式;

    最大乘积 f[i,j]=max(f[i-1,j-1]*w[j,i])  (0<=k<=n)(1<j<=i<=n)

    巴比伦塔、硬币问题、最长前缀、砝码秤重、书的复制、硬币组成问题;

    花店橱窗布置问题(IOI99试题);

    Tom的烦恼 :可用数据结构优化区间最值

    数字游戏、统计单词个数(noip)、1的最小操作序列;

    积木游戏(NOI’97):f[I,j,k]表示第i个积木(k面朝上)放在第j根柱子上的最大高度和则:f[I,j,k]=max{f[x,j,z],f[x,j-1,z]}+h[I,k].

    复杂度O(n^2m)

    化工厂装箱员:CEOI 2005 service

    打鼹鼠

    描述 Description

    根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为(i,j)的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格,机器人不能走出整个n*n的网格。游戏开始时,你可以自由选定机器人的初始位置。

    现在你知道在一段时间内,鼹鼠出现的时间和地点,希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

    输入格式 Input Format

    文件第一行为n(n<=1000), m(m<=10000),其中m表示在这一段时间内出现的鼹鼠的个数,接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻,在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。

    输出格式 Output Format

    输出文件中仅包含一个正整数,表示被打死鼹鼠的最大数目。

    样例输入 Sample Input

    2 2

    1 1 1

    2 2 2

    样例输出 Sample Output

    1

    隐形的翅膀

    背景 Background

    小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀,他也想要。
    (小杉是怎么看到的?……)

    描述 Description

    天使告诉小杉,每只翅膀都有长度,两只翅膀的长度之比越接近黄金分割比例,就越完美。
    现在天使给了小杉N只翅膀,小杉想挑出一对最完美的。

    输入格式 Input Format

    每组测试数据的
    第一行有一个数N(2<=N<=30000)
    第二行有N个不超过1e5的正整数,表示N只翅膀的长度。
    20%的数据N<=100

    输出格式 Output Format

    对每组测试数据输出两个整数,分两行,表示小杉挑选出来的一对翅膀。
    注意,比较短的在前,如果有多对翅膀的完美程度一样,请输出最小的一对。

    样例输入 Sample Input

    4

    2 3 4 6

    样例输出 Sample Output

    2

    3

    Vijos 1198 最佳课题选择:if j-k>=0 then f[I,j]:=Min(f[i,j],f[i-1,j-k]+time(i,k))

    IOI 2000 邮局问题

    [问题描述]

    按照递增顺序给出一条直线上坐标互不相同的n个村庄,要求从中选择p个村庄建立邮局,每个村庄使用离它最近的那个邮局,使得所有村庄到各自所使用的邮局的距离总和最小。

    试编程计算最小距离和,以及邮局建立方案。

    思路一:现以f[i,j]表示安排前i个村庄使用前j个邮局,通过某种安排手段,使这i个村庄分别到这j个邮局中最近的一个的距离之和的所取到的最小值。 F[i,j]=min{f[k,j-1]+c[k+1,i]}(1<=k<i)

    C[A,B]表示分配A至B这(B-A+1)个村庄使用一个新的邮局,通过某种安排新邮局的手段,使A至B这(B-A+1)个村庄分别到这个新邮局的距离之和所取到的最小值。

    那么,怎么求c数组呢?此问题相当于邮局数为1的原问题的一种特殊情况。即,给定N个村庄的X坐标,要求安排一个邮局,使各村庄到该邮局的距离和为最小,求邮局坐标。

    引论(尽管题目条件已给出了这个限制,证一下也无妨):最优解必定可使得邮局坐落在一个村庄上。

          

    假设将邮局建在A和B村庄之间,与A相距a,与B相距b,A左边共有x个村庄(含A)使用该邮局,它们到A的距离和为SA;B右边共有y个村庄(含B)使用该邮局,它们到B的距离和为SB。则cost=SA+SB+ax+by.

    但若建在A处,则costA=SA+SB+(a+b)y;

    但若建在B处,则costB=SA+SB+(a+b)x.

    当x=y时,三中方案皆可以;

    当x>y时,建在A处更优;

    当x<y时,建在B处更优。

    由此可见,最优解必定可使得邮局坐落在一个村庄上。

    结论:对于n个村庄,邮局建在第(n div 2+1)个村庄最优。

    证明:有引论知,对于n=x+y,若x>y,则邮局选址会不断往左靠,直到x=y。x<y时也如此。即总有往中间靠的趋势!

    思路二:f[i,j]表示第j个邮局建在第i个村庄的最小值。

    F[I,j]:=min{f[k,j-1]+c[k,i]}.(1<=k<i)

    C[a,b]表示在相邻邮局建在a和b村庄时,a到b间的各村庄到所对应邮局的最小距离和。

    思路三:四边形不等式优化。(网上有人这样讲,但目前我没了解)

     

    三、区间动态规划(剖分问题)

    石子合并

    变式:能量项链,多边形剖分,最少矩阵乘法次数

    取数游戏、加分二叉树

     

    决斗

    在路易十三和红衣主教黎塞留当权的时代,发生了一场决斗。N(2<=n<=500)个人站成一个圈,依次抽签。抽中的人和他右边的人决斗,负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息,但“A赢了B”这种关系没有传递性。例如,A比B强,B比C强,C比A强。如果A和B先决斗,C最终会赢,但如果B和C决斗在先,则最后A会赢。显然,他们三人中的第一场决斗直接影响最终结果。

    假设现在n个人围成一个圈,按顺序编上编号1~n。一共进行n-1场决斗。第一场,其中一人(设i号)和他右边的人(即i+1号,若i=n,其右边人则为1号)。负者被淘汰出圈外,由他旁边的人补上他的位置。已知n个人之间的强弱关系(即任意两个人之间输赢关系)。如果存在一种抽签方式使第k个人可能胜出,则我们说第k人有可能胜出,我们的任务是根据n个人的强弱关系,判断可能胜出的人数。

    编号为x的人能从所有人中胜出,必要条件是他能与自己“相遇”,即把环看成链,x点拆成两个在这条链的两端,中间的人全部被淘汰出局,x保持不败。这样,在连续几个人的链中,只须考虑头尾两个人能否胜利会师,中间的则不予考虑,从而少了一维状态表示量。设meet[i,j]记录i和j能否相遇,能相遇则为true,否则为false。状态转移方程为

          

    或这这么写:F[I,j] = (f[I,k] and f[k,j]) and (e[I,k] or e[j,k]), i<k<j

     

    小H的小屋

    【问题描述】

    小H发誓要做21世纪最伟大的数学家。他认为,做数学家与做歌星一样,第一步要作好包装,不然本事再大也推不出去。为此他决定先在自己的住所上下功夫,让人一看就知道里面住着一个“未来的大数学家”。

    为了描述方便,我们以向东为x轴正方向,向北为y轴正方向,建立平面直角坐标系。小H的小屋东西长为100Hil(Hil是小H自己使用的长度单位,至于怎样折合成“m”,谁也不知道)。东墙和西墙均平行于y轴,北墙和南墙分别是斜率为k1和k2的直线,k1和k2为正实数。北墙和南墙的墙角处有很多块草坪,每块草坪都是一个矩形,矩形的每条边都平行于坐标轴。相邻两块草坪的接触点恰好在墙上,接触点的横坐标被称为它所在墙的“分点”,这些分点必须是1到99的整数。

    小H认为,对称与不对称性的结合才能充分体现“数学美”。因此,在北墙角要有m块草坪,在南墙角要有n块草坪,并约定m≤n。如果记北墙和南墙的分点集合分别为X1,X2,则应满足X1含于X2,即北墙的任何一个分点一定是南墙的分点。

    由于小H目前还没有丰厚的收入,他必须把草坪的造价降到最低,即草坪的占地总面积最小。你能编程帮他解决这个难题吗?

    【输入文件】

    仅一行,包含4个数k1,k2,m,n。k1和k2为正实数,分别表示北墙和南墙的斜率,精确到小数点后第一位。m和n为正整数,分别表示北墙角和南墙角的草坪的块数。

    【输出文件】

    一个实数,表示草坪的最小占地总面积。精确到小数点后第一位。

    【约定】

    2≤m≤n≤100

    南北墙距离很远,不会出现南墙草坪和北墙草坪重叠的情况

    【样例输入】

    0.5 0.2 2 4

    【样例输出】

    3000.0

          

    【评分标准】

        对于每个测试点,如果你的结果与标准答案的误差不超过0.1,则可以得到该测试点的满分,否则得0分。

    朴素的动态规划时间复杂度为O(L^2 · m^2 · n),但是此题恰好可以卡过。

    首先预处理g[k][i]即把东西长度为k的区域分给南墙,分成i块的最小面积。
    可以轻易得出g[k][i] = g[k`][i - 1] + (k - k`)^2 * K2 (k` < k)。

    然后在计算f[k][i][j]即把东西长度为k的区域分给南北两边的墙,北墙分成i块,南墙分成j块的最小面积。
    则有:f[k][i][j] = f[k`][i - 1][j`] + g[k - k`][j - j`] (k` < k, j` < j)。 最后的答案就是f[100][m][n]。

    可以发现之前的方程具有决策单调性。

    也就是说,f[k][i][j]的决策k`、j`一定不小于f[k][i - 1][j]的决策k``、j``,
    那么每次枚举k`、j`的时候就可以从k``、j``开始枚举。

    这样可以把时间复杂度降到O(L^2 · m · n)。

    F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k)

     

    多边形-讨论的动态规划

    多角形是一个单人玩的游戏,开始时有一个N个顶点的多边形。如图,这里N=4。每个顶点有一个整数标记,每条边上有一个“+”号或“*”号。边从1编号到N。

      第一步,一条边被拿走;随后各步包括如下:

    选择一条边E和连接着E的两个顶点V1和 V2;

    得到一个新的顶点,标记为V1与V2通过边E上的运算符运算的结果。

    最后,游戏中没有边,游戏的得分为仅剩余的一个顶点的值。

    当OP=‘+’

    Fmax(i,j)=max{fmax(i,k)+fmax(k+1,j)}

    Fmin(i,j)=min{fmin(i,k)+fmin(k+1,j)}

    当OP=‘*’

          

    括号序列

          

     

    方块消除(poj1390)

    Jimmy最近迷上了一款叫做方块消除的游戏. 游戏规则如下:n个带颜色方格排成一列,相同颜色的方块连成一个区域(如果两个相邻的方块颜色相同,则这两个方块属于同一个区域). 游戏时,你可以任选一个区域消去.设这个区域包含的方块数为x,则将得到x^2的分值.方块消去之后,右边的方格将向左移动.

    虽然游戏很简单,但是要得到高分也不是很容易.Jimmy希望你帮助他找出最高可以得到多少分.

    解题方法:

    f[i,i-1,0]:=0

    f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),

                  f[i,p,k+len[j]]+f[p+1,j-1,0]}

    ans:=f[1,m,0]

     

    四、坐标动态规划(平面、地图)

    免费馅饼(模型转化)

    NOI 1998

    F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];

     

    #可以忽略

    F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;

    ——加单调队列优化的。

     

    其他题目:方格取数、子矩阵问题、数字三角形、打砖块、滑雪、城堡、祝福、街道路径条数

    棋盘切割

    一、问题描述

    将一个8×8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

          

    原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。

    均方差 , 其中平均值 , xi为第i块矩形棋盘的总分。

    请编程对给出的棋盘及n,求出的最小值。

    输入

    第1行为一个整数n(1<n<15)。

    第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

    输出

    仅一个数,为(四舍五入精确到小数点后三位)。

    样例输入

    3

    1 1 1 1 1 1 1 3

    1 1 1 1 1 1 1 1

    1 1 1 1 1 1 1 1

    1 1 1 1 1 1 1 1

    1 1 1 1 1 1 1 1

    1 1 1 1 1 1 1 1

    1 1 1 1 1 1 1 0

    1 1 1 1 1 1 0 3

    样例输出

    1.633

          

    二、初步分析

    本题的实质是求一种最优的棋盘分割方式,使得每块棋盘与平均值的差值之和最小。

    首先我们必须明确几个条件(关键字),这样对我们理解题意进而采取正确的算法解决问题大有帮助:

    1. 均方差:在实际编程的过程中,由于n是定值,实际只需求(Xi-X)的和的值作为参数,以此简化程序的计算及存储的空间。
    2. 本题提供固定的8×8棋盘,并不算大,这是本题有解的重要条件,并且给我们一个暗示:以棋盘格子为存储单位,将有很大的自由度。

            于是我们开始考虑算法:对比八皇后问题的复杂度,我们不难看出这道题需要搜索更多的内容,在时间上搜索算法实不可取;因此,只能使用动态规划实现本题。经过分析,不难发现本题符合最优化原理:即若第i次分割为最佳分割,则第i-1次分割为且必为最佳;定义函数F[i,j][i’,j’]为[i,j]、[i’,j’]分别为左上、右下角的棋盘的最优值,F0[i,j][i’,j’]为[i,j]、[i’,j’]分别为左上、右下角的棋盘值,探寻函数F[i,j][i’,j’]的动态转移方程。

            下面分析分割方式。当我们进行第i次分割时不外乎以下四种方式:

          

    逐一进行分析:(图3.4-3)

    横割方式:

          a、第i次切割将棋盘分为上i-1个棋盘和下1个棋盘(图(a))

                A1=F0[i1,j1][i’,j2]+F[i’+1,j1][i2,j2]

          b、第i次切割将棋盘分为下i-1个棋盘和上1个棋盘(图(b))

                 A2=F[i1,j1][i’,j2]+F0[i’+1,j1][i2,j2]

    竖割方式:

          c、第i次切割将棋盘分为右i-1个棋盘和左1个棋盘(图(c))

                A3=F[i1,j1][i2,j’]+F0[i1,j’+1][i2,j2]

          d、第i次切割将棋盘分为左i-1个棋盘和右1个棋盘(图(d))

                A3=F0 [i1,j1][i2,j’]+F [i1,j’+1][i2,j2]

    状态转移方程为:

          F[i1,j1][i2,j2]=min{A1,A2,A3,A4}    (1<=i1,j1<=8,i1<=i2<=8,j1<=j2<=8,2<=k<=n)

    其中k代表分割的棋盘数,单调递增,因此第k次分割只与k-1次的结果有关,所以每做完第k次对棋盘的规划F0ßF。由此节省下许多空间。

    三、程序实现

          下面我们讨论程序实现的具体步骤与代码的优化。

           首先在读入过程段我们进行准备工作,累加计算出F0并统计出棋盘每个格子值之和S来计算平均数Average。

    s:=0;
    for i:=1 to 8 do 
    for j:=1 to 8 do begin
      		read(f[i,j][i,j]); ss+f[i,j][i,j];	{读入棋盘每个格子的值,并统计其和}
    		for i1:=1 to i do 				{枚举左上方坐标i1,j1}
    			for j1:=1 to j do
     				for i2:=i to 8 do
    					for j2:=j to 8 do			{枚举右上方坐标i2,j2}
    						if  (i1<>i) or (j1<>j) or (i2<>i) or (j2<>j)
    							the f[i1,j1][i2,j2]f[i1,j1][i2,j2]+f[i,j][i,j];
    	end;

    在套用循环算出F0[i1,j1][i2,j2]的值,此处不再赘述。

    然后用动态规划求解:

    for i:=2 to n do begin	  						{分阶段,第i次分割}
    	for i1:=1 to 8 do
    	 for j1:=1 to 8 do
    	  for i2:=i1 to 8 do 
     	   for j2:=j1 to 8 do begin					{确定坐上、右下角坐标}
    			F[i1,j1][i2,j2]:=max;
    			for i’:=i1 to i2-1 do begin
     			 	# 计算A1,A2;
    				F[i1,j1][i2,j2]:=min{A1,A2};
    			end;
    			for i’:=i1 to i2-1 do begin
     			 	# 计算A3,A4;
    				F[i1,j1][i2,j2]:=min{F[i1,j1][i2,j2],A3,A4};
    			end;
    		end;
    	F[0]:=F;
    end;

    显然问题的解为:

    三、小结

    本题是极有代表性的动态规划题型,较之NOI99的其他题目算是比较简单的。此题的思路简单而明了,没有太多限制条件让人梳理不清,空间的自由度很大,唯一的限制便是运行时间。

    所谓窥一斑可见全豹,从本题的思考过程中,我们不难总结出应用动态规划算法的一般思路及步骤:

    1. 确定算法,整体估计可行度。一般从两方面着手:时空复杂度和最优化原理。
    2. 建立模型,考虑可能出现的情况。
    3. 建立动态转移方程。

    程序实现及代码优化。

     

    ZOJ cheese(竟然没给数据范围?!)

    给出一个地图,每个点上有相应数量的cheese,从(0,0)开始,每到一个格子就把这个格子里的cheese吃光,每走一步方向只能是上下左右,每一步最多的格子数为k,每一步之后的一格所包含的cheese数量要比之前一格多…怎样才能使得所得的cheese数最多呢,输出最多的cheese数.

     

    五、树型动态规划

    典型题目:选课、二叉苹果树、贪吃的九头龙、聚会的快乐、皇宫看守、APIO2007风铃、访问术馆

     

    ioi2005河流

    先多叉转二叉。

    进行了相关的转化之后,设f(i,j,k)表示在新树中,以i结点为根的子树中,分配k个加工厂。并且离i结点最近的加工厂在j结点的情况下。i结点及其子树内的所有产品,加工所需要的费用。 转移方程很容易就可以写出来:

          

    总时间复杂度为O(N2K2)。

     

    有向树k中值问题

    给定一棵有向树T,树T中每个顶点u都有一个权w(u);树的每条边(u,v)也都有一个非负边长d(u,v)。有向树T的每个顶点u可以看作客户,其服务需求量为w(u)。每条边(u,v)的边长d(u,v)可以看作运输费用。如果在顶点u处未设置服务机构,则将顶点u处的服务需求沿有向树的边(u,v)转移到顶点v处服务机构需付出的服务转移费用为w(u)*d(u,v)。树根处已设置了服务机构,现在要在树T中增设k处服务机构,使得整棵树T 的服务转移费用最小。

    对于给定的有向树T,编程计算在树T中增设k处服务机构的最小服务转移费用。

    先转化成二叉树,然后动态规划。

    f[x,u,j](以x为根的子树到u的最小费用)=min{ f[lc[x],u,i]+f[rc[x],u,j-i]+w[x]*d[x,u], f[lc[x],x,i]+f[rc[x],u(想想转二叉树),j-i-1]},

    同ioi2005河流 。

    记忆化搜索递规求解。至于独立中值,只有一点不同,自己想吧。

     

    NOI2006 网络收费、NOI2006千年虫

     

    NOI2003逃学的小孩

    问题抽象

    本题题意很明确,即在一棵树中,每条边都有一个长度值,现要求在树中选择3个点X、Y、Z,满足X到Y的距离不大于X到Z的距离,且X到Y的距离与Y到Z的距离之和最大,求这个最大值。

    很显然,该题的结构模型是一棵树,而且数据量很大,很容易把这题的方法向在树形结构上使用动态规划上靠拢。考虑任意节点a时,很容易发现,如果以这个点作为题目中要求的节点Y,那么只需要求出离这点最远的两个节点即可。但是在树形结构上,计算出离某个节点最远的两个节点需要的复杂度,而我们并不知道哪个点是答案中的节点Y,所以必须枚举这个点,这样一来,时间复杂度就成了,在N=200000时会严重超时,因此这个方法是不可行的。

    枚举Y点的话,会超时,是否就无法加上枚举的思想呢?可以多尝试一些思路。观察这样一棵树:

          

    可以把点3当作点X,点1当作点Y,点6当作点Z,这样就可以得到最大值了。因为|XY|=|YX|,故只需考虑YX和YZ这两条路就可以了。在图中来观察这两条路,可以发现分别是这样走的:YX:1à2à3,YZ:1à2à4à6。来比较这两条路的行程,可以发现,都是从1先到2,然后再分开走各自的路,而且满足从2以后的经过的节点,没有重复的节点。为了方便,我们形象地将点2称为分叉点。如果枚举分叉点,能不能得到一个高效的算法呢?来尝试分析这种想法。

    枚举分叉点

    将某个点a当作分叉点时,以其为根构造一棵树,对节点Y,就有两种情况:1Y就是节点a;2Y在a的某个孩子节点的子树上。对于情况1,可以把它转化为情况2,只需给a加一个空的孩子节点,认为它和a之间的距离是0即可。既然a是分叉点,那么X和Z就不能在同一棵子树上,X和Y,Y和Z也不能在同一棵子树上。题目中要求的是使|XY|+|YZ|最大,也就是要求2|Ya|+|Za|+|Xa|最大。至此,思路已完全明确,对于以a为分叉点的情形,只需求出到a的最远的3个点,而且这3个点分别处于a的3棵不同的子树之中。如果采用枚举分叉点的方法的话,每次都需要的计算才行,时间复杂度就又成了。

    两次遍历

    这里,需要改变一下思路。以点1为根,计算出要求的值后,不去枚举其它的节点,而把这棵树再遍历一遍,进行一次BFS,深度小的先访问,深度大的后访问,就保证了访问到某一个节点的时候,其父亲节点已经被访问过了。假设我们现在访问到了点a,我们现在要求的是距点a的3个最远的点,且这3个点到a的路径上不经过除a外的相同节点。显然,这3个点要么位于以a为根的子树中,要么位于以a为根的子树外。如果在以a为根的子树外,那么是一定要通过a的父亲节点与a相连的。至此,思路逐渐清晰起来。此次遍历时,对于点a,检查其父亲节点,只需求出到其父亲节点的最远的,且不在以a为根的子树中的那点即可,再与第一次遍历求得的值进行比较,就可以求出以该点为分叉点时,|XY|+|YZ|的最大值了。具体方法为,每个点记录最大的两个值,并记录这最大的两个值分别是从哪个相邻节点传递来的。当遍历到其某个孩子节点时,只需检查最大值是否是从该孩子节点传递来的,如果是,就取次大值,如果不是,就可以取最大值。这样一来,该算法的时间复杂度和空间复杂度都为,是个非常优秀的算法。

    注意

    这里提醒大家注意一点,计算过程中的值和最后的结果可能会超过长整型的范围,所以这里需要使用int64或者double类型。

    对于树必须进行两次遍历,才能求得最终的最大值。该例题的分析中提出了分叉点的想法,是比较具有创造性的,需要从多个角度思考。因此,在平时的练习中,当对一道题目束手无策时,可从多个角度思考,创造新思维,使题目得到解决。此题遍历两次的方法具有普遍性,在许多题目中都可以得到应用:记录最大的两个值,并记录是从哪个节点传递来的思想方法。这种遍历两次和记录最大的多个值的思想是值得学习的,也是动态规划在树上进行使用的经典方法。

    本题的树型动态规划复杂度是线形的,但是也有一部分问题,在线形的时间内无法出解。这类问题的变化更多,从状态的确立到状态的转移,都对思考角度有着更高的要求。

     

    六、字符串动态规划

    NOI 2000 古城之谜古城之谜

    Ural 1002 Phone:if exist(copy(s,j,i-j)) then f[i]:=min(f[i],f[j]+1)

    字符串匹配(通配符问题)

    字符串通配(**——)

    给一个带通配符*和?的字符串S,问它能不能匹配字符串T。

    例如,a*b?能够匹配aabc,但是不能匹配aab

       其中*能够匹配0个或任意多个字符;

    ?匹配1个任意字符!

    思路:列表

          a     a     b     c

    a     1     1     0     0

    *     1     1     1     1

    b     0     0     1     0

    ?     0     0     0     1

     

          a     a     b

    a     1     1     0

    *     1     1     1

    b     0     0     1

    ?     0     0     0

          

    本格"?":左上为1则本格为1

    "*":前一行上为1则本格为1,左为1则本格为1

    字母:行列上的字母相同且左上为1,则本格为1

     

    问题:如果T也可以包含通配符呢?

    以f[I,j]=true表示S串中的前I个和串T中的前j个能完全匹配;

    =false表示不能完全匹配

     

    对于两串都有通配符的问题,我认为应该是:

    if (S[I]=’*’ or T[j]=’*’) and (f[I-1,j] or f[I,j-1]) then

        f[I,j]=true

    else if ((S[I]=’?’) or (T[j]=’?’) or (S[I]=T[j])) and f[I-1,j-1] then

        f[I,j]=true

      else f[I,j]=false;

    求大神确认!!

     

    七、贪心动态规划

    快餐问题

    一、问题描述

    Peter 最近在R市开了一家快餐店,为了招揽顾客,该快餐店准备推出一种套餐,该套餐由A个汉堡,B个薯条和C个饮料组成。价格便宜。为了提高产量,Peter从 著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡,薯条和饮料,由于每条生产线每天所能提供的生产时间是有限的、不同的,而汉堡,薯条和饮 料的单位生产时间又不同。这使得Peter很为难,不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序,计算一天中套餐的最大生产量。为简 单起见,假设汉堡、薯条和饮料的日产量不超过100个。

    输入:

    输入文件共四行。第一行为三个不超过100 的正整数A、B、C中间以一个空格分开。第三行为3个不超过100的正整数p1,p2,p3分别为汉堡,薯条和饮料的单位生产耗时。中间以一个空格分开。 第三行为N(0<=0<=10),第四行为N个不超过10000的正整数,分别为各条生产流水线每天提供的生产时间,中间以一个空格分开。  

     输出: 每天套餐的最大产量。

     

    资源分配型动态规划。

    算法1:四维纯动态规划

    较容易想到的方程是:

    F[I,j,k,L]:=f[i-1,j-j0,k-k0,L-L0] and g[I,j0,k0,L0]

    F[I,j,k,L]表示前i条生产线能否生产出j个汉堡、k个薯条、L个饮料。

    g[I,j0,k0,L0]表示第i条生产线能否生产出j0个汉堡、k0个薯条、L0个饮料。

    Ans=max{min{j div a,k div b,L div c} | f[n,j,k,L]=true}

    空间不会暴,但时间复杂度为:O(n*100^6)无法承受!V_V

     

    算法2:三维纯动态规划

    F[I,j,k]表示前I条生产线生产j个汉堡,k个薯条的情况下最多生产饮料的个数。

    g[I,j,k]表示第I条生产线生产j个汉堡,k个薯条的情况下最多生产饮料的个数。

       复杂度为O(n*100^4),还需进一步优化!

       上限优化:利用条件“汉堡、薯条和饮料的日产量不超过100个”优化上限;根据每条生产线的生产能力局部优化关于g[I,j,k]的枚举上限(即5个for循环中的后两个循环的上限)。

     

    算法3:greed+动态规划

    动态规划之前,根据条件“汉堡、薯条和饮料的日产量不超过100个”,用贪心法求极限解,若极限解可行则输出并退出程序。

     

    青蛙过河

    此题方程容易写出:

    if I处有石头F[i]:=min{f[k]}+1 (i-t<=k<=i-s);

    if I处无石头f[i]:=min{f[k]} (i-t<=k<=i-s)

    复杂度为O(L*(t-s)),无法过!

    优化:对于长度大于s*t且无石头的一段,可以缩短变为s*t,因为对于任意长度大于或等于s*t无石头的桥,总可以找到一种方法,能从桥的一端正好跳到另一端。(启示:寻找冗余以求优化)

    证明:

    对于len=st+k(k>0)

    s+k<=t, len=(t-1)s+(s+k);

    t<s+k<=2t-s0<s+k-t<=t-s, len=(t-2)s+[s+(s+k-t)]+t;

    2t-s<s+k<=3t-2s0<(2s+k-2t)<=t-s,

    len=(t-3)s+[s+(2s+k-2t)]+2t;

    ……

    (t-1)t-(t-2)s<s+k<=t^2-(t-1)s0<(t-1)s+k-(t-1)t<=t-s

       Len={s+[(t-1)s+k-(t-1)t]}+(t-1)t;

    由最后一个式子知,若s+k再大,则len>t^2

    t^2=(s+t-s)t=st+(t-s)t,故此时len=(t-s)t+st+kk(kk>0),又回到了最初的分析! ——心血啊…… 

     

    八、多进程动态规划

    CEOI 2005 service

    3 sec64mb

    一个公司有三个移动服务员。如果某个地方有一个请求,某个员工必须赶到那个地方去(那个地方没有其他员工)某一时刻只有一个员工能移动。被请求后,他才能 移动,不允许在同样的位置出现两个员工。从pq移动一个员工,需要花费c(p,q)。这个函数没有必要对称,但是c(p,p)=0。公司必须满足所有的 请求。目标是最小化公司花费。
    输入
    第一行有两个整数L,N(3<=L<=200, 1<=N<=1000)L是位置数 N是请求数。每个位置从1L编号。下 L行每行包含L个非负整数。第i+1行的第j个数表示c(i,j) 并且它小于2000。最后一行包含N个数,是请求列表。一开始三个服务员分别在位置 123
    输出
    第一行包含一个数M表示最小服务花费。第二行包含N个数,第i个数表示哪个员工执行服务任务(123)。如果有多种可能,输出任意一种。
    样例输入
    5 9 
    0 1 1 1 1 
    1 0 2 3 2 
    1 1 0 4 1 
    2 1 5 0 1 
    4 2 3 4 0 
    4 2 4 1 5 4 3 2 1 

    样例输出

    1 2 1 2 2 1 3 1 3

    解题方法:

    Min( f[i,j,k], f[i-1,j,k] + c[t[i-1],t] )

    Min( f[i,t[i-1],k], f[i-1,j,k] + c[j,t] )

    Min( f[i,j,t[i-1]], f[i-1,j,k] + c[k,t] )

     

    Vijos1143 三取方格数

     

    九、状压动态规划

    炮兵阵地

    APIO2007 动物园

    题目简述:N个动物围成一个环,有K个小朋友,每个小朋友可以看到五个连续的动物,每个小朋友都有自己喜欢或讨厌的动物,当有一个自己讨厌的动物被移走或能看到一个自己喜欢的动物时,这个小朋友就会高兴。求最优的移走动物的方案,使得最多的小朋友高兴。

    主要要注意的就是因为是环,所以前4个点的状态必须一开始固定死,以下是解题报告(来源:here is rj):

    动态规划,用二进制表示动物的取舍。

    F[i][j] 表示从1到i+4的动物,其中i到i+4的动物的取舍状态为j时,最多

    的高兴的小朋友的数目。

    状态转移方程为:

    F[i][j]=max{F[i-1][(j<<1)&31],F[i-1][((j<<1)&31)|1]}+num[i][j];

    j的二进制串中,最后一位表示i,倒数第二为表示i+1,以此类推。

    num[i][j]为看到i到i+4的动物的小朋友在j的状态下高兴的数目;

    边界条件:F[0][j]=0;

    目标函数:max{F[N][j]}(0<=j<32);

    不过,这是环形,因此要枚举固定开头的4个动物。

    算法分析:

    动规的阶段为O(2^4),状态为O(2^5*N),状态转移O(1);

    总的时间复杂度为O(2^9*N);

    基本可以承受。

    {浅陋看法:此题还可加强N的范围,这时可以按小孩逐个转}

     

    购物(IOI95-2)

          可将每种物品按5进制编码。(5为每种物品数的上限)

    Roger游戏任务一(CTSC98 Day2 4)

          一个正方体在一个方格内的状态只有24种,而且可以通过顶面和前面来表示,这样用3维的状态(x,y,p)就可以解决,p为1到24种状态中的一种。

     

    十、判定型动态规划

    其实,这类问题归属递推问题。针对一些不满足最优性原理的题设计。

    Mod 4最优路径

     

    十一、目标型动态规划

    CEOI98 subtra:F[I,j]:=f[I-1,j+a] or f[i-1,j-a]

    积木城堡、Vijos 1037搭建双塔问题、多诺米骨牌、垃圾陷阱

     

    十二、概率动态规划

    聪聪和可可(NOI2005)

    题目的主要思想是动态规划(记忆化搜索)。设F[X,Y]表示可可在X点,聪聪在Y点时Gameover的平均步数。在已知可可位置时,聪聪的移动方法是题目本身规定的。不妨设G[X,Y]表示可可在X点,聪聪在Y点时,聪聪下一步移动到的位置,而T[X]表示与X相连的点的个数,S[X][I]表示与X相连的第I个点。

    那么有状态转移方程F[X,Y] = (F[S[X][K],G[X,Y]] + F[X,G[X,Y]]) /( T[x] + 1) + 1

    关键是对G[X][Y]的初始化,用Floyed效率太低,大数据肯定超时。Heap+Dijkstra可以接受,复杂度为O((N+ElogN)。

    最好的方法就是BFS。求权值为1的任两点间最短路的时间复杂度为ONE)。动态规划的时间复杂度为ON2)。整个算法的时间复杂度为ONE)。

     

    血缘关系(妖怪家族)

     

    十三、二次动态规划(双重动态规划)

    基因序列(Gen.pas

    Genotype 是一个有限的基因序列。它是由大写的英文字母A-Z组成,不同的字母表示不同种类的基因。一个基因可以分化成为一对新的基因。这种分化被一个定义的规则集合所控制。每个分化的规则可以用三个大写字母A1A2A3表示,含义为基因A1可以分化成A2A3。我们用S代表特种基因,繁殖genotype是从特种基因序列开始。根据给定的规则,它由被选择控制规则对基因不断进行繁殖而成。 现在的问题是,从文件中读入一个定义的规则集和一个想生成的genotypes 单词序列,对每一个给定的 genotype,根据给定的分化规则,检查它是否能从某一个确定特种基因序列生成,如果能,找到最小的序列长度。

    输入(GEN.IN

    文件的第一行有一个整数n, 1 <= n <= 10000。下面n 每一行为一个分化规则,这些规则都由包含A Z的三个大写字母组成。接下来有一个整数k, 1 <= k <= 10000。接下来的k 行有一个 genotypeGenotype由没有空格的单词组成,最多100 个英文大写字母。

    输出(GEN.OUT

    在文件中有k,在第I行应写入:一个正整数――需要生成第Igenotype的最小长度;或者单词 NIE, 如果不能生成对应的genotype

    输入样例                        输出样例:

    6                                                       3

    SAB                                                 1

    SBC                                                 NIE

    SAA

    ACA

    BCC

    CBC

    3

    ABBCAAABCA

    CCC

    BA

    解题报告:

    这是一道有些难度的动态规划题。因为它两次用到了动态规划,最容易想到的是用g[I]表示目标状态前I个字母可以转变成的最小长度,那么g[I]=min{g[j]+1},其中a[j+1..i]是可以转变为一个S的字串。这时问题就很自然的转到了如何确定这样的序列。

    我们用f[I,j,ch]表示目标序列的第I位到第j位可以压缩为字母ch,那么如果存在f[I,j1,ch1]f[j1+1,j2,ch2],并且条件中有chch1ch2,则f[I,j,ch]=true。这样问题就解决了。时间复杂度为O(len^3*26^2),还是承受的起的,但是空间复杂度就较高了,所以我们有必要对状态的表示进行优化。我们用一个26位的二进制数表示状态,这样就只需一个长整型的数即可表示状态。

    此题的解决是一步步倒推得到的。考试时这种思考方式非常重要。只要抓住了题目的本质,理清思路就可以解决问题。

    const s:array['A'..'Z']of integer=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26);
    var f:array[1..100,1..100]of longint;
        i,j,l,k,n,len,c1,c2:integer;
        g:array[1..26,1..26]of longint;
        c:Array[0..100]of integer;
        st:string;
    procedure init;
    begin
        assign(input,'gen.in');reset(input);
        readln(n);
        for i:=1 to n do
          begin
            readln(st);
            g[s[st[2]],s[st[3]]]:=g[s[st[2]],s[st[3]]]+1 shl (s[st[1]]-1);//G[i,j]用二进制表示字符i,j能转化到的字符
          end;
    end;
    procedure 动态规划;
    begin
        len:=length(st);
        for i:=1 to len do
          for j:=1 to len do f[i,j]:=0;                                           //F[i,j]用二进制表示字符的第i位到第j位能转化到的字符
        for i:=1 to len do f[i,i]:=1 shl (s[st[i]]-1);                    //i=j的情况
        for i:=1 to len-1 do f[i,i+1]:=g[s[st[i]],s[st[i+1]]];      //i+1=j的情况
        for L:=3 to len do                                                           //长度
         for i:=1 to len-L+1 do                                                    //起始i
          for j:=i to i+L-2 do                                                       //枚举分割点
           for c1:=1 to 26 do
            if (f[i,j] and (1 shl (c1-1))>0)then
             for c2:=1 to 26 do
              if (f[j+1,i+L-1] and (1 shl (c2-1))>0)then               //两段分别能达到c1,c2
               f[i,i+L-1]:=f[i,i+L-1] or g[c1,c2];                            //集合的合并
        for i:=1 to len do c[i]:=0;
        c[0]:=1;
        for i:=1 to len do
          for j:=0 to i-1 do
            if (c[j]<>0)and(f[j+1,i] and (1 shl 18)>0)and((c[i]=0)or(c[i]>c[j]+1))then
              c[i]:=c[j]+1;                                                               //C[i]表示前i个字符转化为'S'的最少个数
        if c[len]=0 then writeln('NIE')else writeln(c[len]-1);
    end;
    procedure main;
    var i:integer;
    begin
        readln(k);
        for i:=1 to k do
          begin
            readln(st);
            动态规划;
          end;
    end;
    begin
    init;
    assign(output,'gen.out');rewrite(output);
    main;
    close(input);close(output);
    end.

    此处状压,妙!

    鄙人认为此题归属“区间动态规划”+二次动态规划

     

    其他题目:小胖办证(买票)、树中各点的最远点、城市交通(似乎还可以拆点求最短路)

     

    十四、递推问题

    核电站问题

      一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。
      任务:对于给定的N和M,求不发生爆炸的放置核物质的方案总数。

    Input
    该题有多组测试数据,每组数据一行,两个正整数N,M( 1<N<50,2≤M≤5)

    Output
    每组数据只输出一个正整数S,表示方案总数。

    Sample Input
    4 3

    Sample Output
    13

     

    for i:=m+1 to n do a[i]:=2*a[i-1]-a[i-m-1];

     

    数的划分、情书抄写员

    错位排列

    f:=(i-1)(f[i-2]+f[i-1]);

    f[n]:=n*f[n-1]+(-1)^(n-2);

     

    直线分平面最大区域数

    f[n]:=f[n-1]+n

         :=n*(n+1) div 2 + 1;

     

    折线分平面最大区域数

    f[n]:=(n-1)(2*n-1)+2*n;

     

    凸多边形分三角形方法数

    f[n]:=C(2*n-2,n-1) div n;

    对于k边形

    f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)

    二叉树数

    出栈序列

    在原始序列中有i个数,堆栈中有j个数时的,通过pop和push操作能得到的序列数,定义为f[i,j],则本题求的是f[n,0]。       

          f[i,j]=f[i-1,j+1]+f[i,j-1]  {push操作  +  pop操作}                 

         f[0,1..n]=1             

         f[1..n,-1]=0            

     

    Catalan数列一般形式

    1,1,2,5,14,42,132

    f[n]:=C(2k,k) div (k+1);

     

    彩灯布置

    有n盏位置固定的彩灯排列成圆形,要用m种颜色去着色,求使相邻的彩灯着不同颜色的方案数。

    f(n)=(m-2)*f(n-1)+(m-1)*f(n-2)

    盒子与球

    现有r个互不相同的盒子和n个互不相同的球,要将这n个球放入r个盒子中,且不允许有空盒子。问有多少种方法?

    例如:有2个不同的盒子(分别编为1号和2号)和3个不同的球(分别编为1、2、3号),则有6种不同的方法:

    1号盒子  1号球 1、2号球 1、3号球  2号球 2、3号球  3号球

    2号盒子 2、3号球  3号球  2号球 1、3号球  1号球 1、2号球

     输入格式 Input Format 

       两个整数,n和r,中间用空格分隔。(0≤n, r≤10)

     输出格式 Output Format 

       N

    样例输入 Sample Input  

       3 2

    样例输出 Sample Output  

       6

     

    解题方法

    f[i,1]:=1;

    f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);

    另一种解法:

    盒子相同,球不同的问题,并且盒子不允许有空

    f[i][j]表示i个小球放入放入前j个盒子的不同方法。那么递推公式应该是

      F[I][J]=F[I-1][J]*j+f[I-1][J-1]

    解释一下:把i个小球放入j个盒子的方案总数等价于第j个盒子本来是空的,把第i个小球放入(f[i-1][j-1]),或者是原来前j个盒子每个盒子都不是空的,那么根据乘法原理应该有(f[i-1][j]*j)的方案总数。

    盒子相同而球不同的方案,这道题目把它改成了球也不同,盒子也不同了。实际上,我们在遇到这道题目的时候可以假设一下,假设箱子相同,那么最后的答案会是多少?求出了这个答案,最后只要乘以一个箱子的全排列也就ok

    Josephus问题的数学方法

    摘自:http://baike.baidu.com/view/213217.html?fromTaglist

        我们知道第一个人(编号一定是(m-1) mod n) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m mod n的人开始):

      k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2

      并且从k开始报0

      现在我们把他们的编号做一下转换:

      k --> 0

      k+1 --> 1

      k+2 --> 2

      ...

      ...

      k-2 --> n-2

      k-1 --> n-1

      变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x'=(x+k) mod n

      如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下面写递推公式:

      令f表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]

      递推公式

      f[1]=0;

      f=(f+m) mod i; (i>1)

      有了这个公式,我们要做的就是从1-n顺序算出f的数值,最后结果是f[n]。因为实际生活中编号总是从1开始,我们输出f[n]+1

      由于是逐级递推,不需要保存每个f,程序也是异常简单:

    var n,m,i,s:integer;
      begin
      write('N M =');
      read(n,m);
      for i:=2 to n do
      s:=(s+m) mod i;
      writeln('The winner is ',s+1);
      end. 

     

    排列动态规划

    *1*逆序对个数为k的排列数:

    f[I,j]表示i排列中逆序个数为j的排列数,

    f[i][j] =   可以用前缀和优化

    或者f[i][j] = f[i][j-1]+f[i-1][j]-f[i-1][j-i-1]

    *2*Ysq pf

    用斐波那契数列做的背景,其实和它没一点关系,就是问你用 n 个不同数去构一个长度为 p 的数列的不同方案数,且每个数至少出现一次,如果要重复出现,则中间至少要隔m 个数。

      比较简单的 动态规划,设二维状态 i,ji 表示数列的长度,j 表示前面使用了几个数,所以转移就是 f[ij]=f[ij]+[f[i-1j-1]*n-j+1),如果 j>mf[ij]还可以从 f[i-1j]*j-m)转移过来

     

    十五、计数问题

    统计正方形和长方形个数

    方法:先确定长,并求出该长度下的情况数,再确定宽。

    乘法原理。

    总数tot:=

           =n*m*(n+1)*(m+1)/4.

    正方形数x:= 

    长方形数y:=tot-x。

    砝码称重

    现有1g、2g、3g、5g、10g、20g的砝码各若干枚,问用这些砝码可以称出多少种不同的重量。(设砝码的总重量不超过1000克,且砝码只能放在天平的一端)

    这一题 f[i][i1]=f[i-1][i1-n*a[i]] 表示的是用前i个砝码表示i1这个重量如果能表示的话就记录一下,因为已经告诉了最大可得到的重量是1000所以i1的范围就知道了,当然也可以自己算可以节省一些时间

                     f[f[0]+1]=f[j]+k*w[j];

                     (1<=i<=n;  1<=j<=f[0]; 1<=k<=a[i];)

    2k进制数

    计数问题2  陨石的秘密

    -----陨石的秘密(排列组合中的计数问题)

    Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];

    F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);

    问题描述

    公元11380年,一颗巨大的陨石坠落在南极。于是,灾难降临了,地球上出现了一系列反常的现象。当人们焦急万分的时候,一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察,科学家们发现陨石上刻有若干行密文,每一行都包含5个整数:

    1 1 1 1 6

    0 0 6 3 57

    8 0 11 3 2845

    著名的科学家SS发现,这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算,他定义了一种SS表达式:

    1. SS表达式是仅由‘{’,‘}’,‘[’,‘]’,‘(’,‘)’组成的字符串。
    2. 一个空串是SS表达式。
    3. 如果A是SS表达式,且A中不含字符‘{’,‘}’,‘[’,‘]’,则(A)是SS表达式。
    4. 如果A是SS表达式,且A中不含字符‘{’,‘}’,则[A]是SS表达式。
    5. 如果A是SS表达式,则{A}是SS表达式。
    6. 如果A和B都是SS表达式,则AB也是SS表达式。

    例如

    ()(())[]

    {()[()]}

    {{[[(())]]}}

    都是SS表达式。

    ()([])()

    [()

    不是SS表达式。

    一个SS表达式E的深度D(E)定义如下:

          

    例如(){()}[]的深度为2。

    密文中的复杂运算是这样进行的:

    设密文中每行前4个数依次为L1,L2,L3,D,求出所有深度为D,含有L1对{},L2对[],L3对()的SS串的个数,并用这个数对当前的年份11380求余数,这个余数就是密文中每行的第5个数,我们称之为“神秘数”。

    密文中某些行的第五个数已经模糊不清,而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

    输入文件(secret.in)

    共一行,4个整数L1,L2,L3,D。相邻两个数之间用一个空格分隔。

    (0≤L1≤10,0≤L2≤10,0≤L3≤10,0≤D≤30)

    输出文件(secret.out)

    共一行,包含一个整数,即神秘数。

    输入样例

    1 1 1 2

    输出样例

    8

    分析解答

    这是一个典型的计数问题。

    动态规划的一个重要应用就是组合计数—如鱼得水,具有编程简单、时空复杂度低等优点。我们自然想到:是否本题也可以用动态规划来解决呢?

    条件的简化

    题目对于什么是SS表达式做了大量的定义,一系列的条件让我们如坠雾中。为了看清SS表达式的本质,有必要对条件进行简化。

    条件1描述了SS表达式的元素。

    条件3、4、5实际上对于()、[]、{}的嵌套顺序做了限制,即()内不能嵌套[]、{},[]内不能潜逃{}。概括起来是两点:SS表达式中括号要配对;{}、[]、()从外到内依次嵌套。

     

    状态的表示

    这是动态规划过程中首先要解决的一个问题。本题的条件看似错综复杂,状态不易提炼出来,实际上,题目本身已经为我们提供了一个很好的状态表示法。

    对于一个表达式来说,它含有的元素是“(”,“)”,“[”,“]”,“{”,“}”,此外,定义了深度这一概念。最简单的一种想法是:按照题目的所求,直接把{}的对数l1、[]的对数l2、()的对数l3以及深度d作为状态表示的组成部分,即用(l1,l2,l3,d)这样一个四元组来确定一个状态。令F(l1,l2,l3,d)表示这样一个状态所对应的神秘数,于是F(L1,L2,L3,D)对应问题答案。此外,我们令G(l1,l2,l3,d)表示含有l1个{},l2个[],l3个(),深度不大于d的表达式个数。显然,F(l1,l2,l3,d)=G(l1,l2,l3,d)-G(l1,l2,l3,d-1)。于是求解F的问题,可以转化为求解G的问题。

     

    状态转移方程的建立

    设当前的状态为(l1,l2,l3,d),根据表达式的第一位的值,分如下三种情况:

    情况一:第一位是“(”,与其配对的“)”位于第i位。设表示这种情况下的总数,、类似定义。

          

    ()将整个表达式分成两部分(图中的ss1和ss2)。根据乘法原理,我们只需对两部分分别计数,然后乘起来即为结果。

    我们设ss1中含有x对{},y对[],z对()。因为ss1外层已经由一对()括起来,故其内部不可再含[]、{},因此x=0,y=0,且ss1的深度不可超过d-1,ss1的数目为G(x,y,z,d-1)=G(0,0,z,d-1)。ss2中含有l1-x=l1个{},l2-y=l2个[],l3-z-1个(),深度不可超过d,ss2的数目为G(l1,l2,l3-z-1,d)。据此,我们写出下面这个式子:

          

    情况一计算的复杂度为O(n^5)。

    情况二:第一位是“[”,与其配对的“]”位于第i位。

          

    与情况一类似可得出

          

    计算复杂度为O(n^6)。

    情况三:第一位是“{”,与其配对的“}”位于第i位。

          

    有如下式子:

          

    这一部复杂度为O(n^7)。

    综合上述三种情况:

          

     

    小结

    本题的时间复杂度为O(n^7),在规定时间内完全可以出解。空间上,若采用滚动数组的方式,可将空间复杂度为n^3,保存也不成问题。本题的难点在于动态规划时情况的划分及处理,当需要建立复杂的状态转移方程时,我们也要保持冷静、抓住要害。

     

    总结至此,祝学习更上一层楼!

    展开全文
  • 常见动态规划算法问题策略分析

    千次阅读 2016-05-28 13:34:37
    本文总结了几种常见动态规划算法的分析策略,但不做案例的具体分析,阅读前最好对这几种算法一定基础了解。

     本文总结了几种常见动态规划算法的分析策略,但不做案例的具体分析,阅读前最好对这几种算法有一定基础了解。


    动态规划策略


    1.动态规划介绍

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

    基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

    由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

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


    2.动态规划求解步骤

    (1)  确定最优解结构

    (2)  递归定义最优解的值

    (3)  自底向上计算最优解的值

    (4)  重构最优解



    几种动态规划算法策略分析


    1.装配线调度问题

    分析:首先确定最优解结构,分析问题可知大致分为两种情况:

    从第一个站出站(j=1)和从第j个站出站(j>=2)。




    当j=1:货物上线后只经过一个站,f1[j]=e1+a1,1

    当j>=2,又可分为跳线和不跳线两种情况:

    不跳线:f1[j]=f1[j-1]+a1,j

    跳线:当货物从f2跳到f1,有一个跳转时间t2,j-1,则:f1[j]=f2[j-1]+t2,j-1+a1,j

    由对称关系,f2[j]可同理得出,最后:

    传输完后,加上自动下线时间x1,x2,总装配时间:


    最后采用自底向上的方法求解算法并递归的输出最优解的值。


    2.矩阵链乘问题

    分析:若只有一个矩阵,无最优解。若大于一个矩阵:对于A1,A2,…,An我们得在和之间加上一个括号使得分开的两个子矩阵链乘积最小,再分别对两个子问题找到最优的划分结果:

    设m[i,j] 为计算矩阵链Ai..j 的乘积所需的最少标量乘法次数。

    若:i=j,不需任何计算,即m[i,j]=0,否则:


    则最终公式为:



    在计算时,采用了自底向上的方法来求解最优解,在求解过程中用一个辅助的数组S[1….n-1,2….n]来记录最优值m[i,j]对应的分割点K,这样能够构造出最优解。最后,借助辅助数组递归的输出最优解的值。


    3.最长公共子序列(LCS)

    分析:可分为最后一个元素相同和不相同两种情况:

    最后一个元素相同:求X[1…m-1]和Y[1…n-1]两个子序列的最长公共子序列。

    最后一个元素不同:求X[1…m-1]和Y[1…n]或者X[1…m-1]和Y[1…n]两个子序列的最长公共子序列。

    令C[i,j]为的LCS的长度,如果i=0或者j=0则LCS=0,则根据LCS的最优子结构特征我们可以构造出:


     

    根据递归式,我们能写出一个递归算法来计算最长公共子序列,由于LCS的子问题过多,所以我们采用自底向上的计算。

     

    在这个过程中,我们需要借组一个数组b[i,j]来记录最优解得构造过程,利用b[i,j]所记录的元素来输出最优解。


    4.最大子段和

    分析:求给定的n个整数(可能但不全为负)a1,a2,…,an, 的i跟j,使 ai 到 aj 的和最大。我们定义b[j]=max(sum(i:j)),

    为从i到j子段的最大子段和。我们比较b[j-1]+a[j]和a[j]的大小,如果b[j-1]<0,显然b[j-1]不是最大子段,此时b[j]=a[j]。反之,我们令b[j-1] + a[j] = b[j],找出最大的子段和。

    则:b[j]=max( b[j-1]+a[j], a[j] ), 1<=j<=n

    由上面的递归公式我们可以写出一个自底向上的递归算法,在算法中我们借助一个变量sum来记录过程中的最大子段和,若此时的b[j]>sum,更新sum中的值,反之,继续求解。直到程序进行完毕,输入sum中的最大子段和。


    5.0-1背包问题

    分析分数背包问题可以采用贪心策略解决,但我们在求解0-1背包问题时,我们只能采用动态规划策略。

    同样地:首先构造最优子结构。令c[i,j]表示利用前i个物品装容量为j的背包所能获得的最大价值,可分两种情况:

    含物品n:去掉第n个物品,用W-wn容量的背包装物品1,2,…,n-1:c[i,j]=c[i-1,j-wi]+vi

    不含物品n:用W容量背包装物品1,2,…,n-1:c[i,j]=c[i-1,j]

    当然,没有物品或没有容量,c[i,j]=0

    则总的递归式:


    有上述递归方程,就可写出相应递归算法,但该递归算法复杂度太高,可用V[0..n,0..W]来保存子问题(i,j)的最大值。b[1..n,1..W]用来保存所做出的最优选择,以便构造最优解。在计算最优解的时候,保存所做出的最优决策,便可得到最优解。



    两种解决策略


    1.自底向上策略

    一般动态规划问题都是基于此策略。在用这种方法时一般需要恰当的定义子问题的规模,使得任何子问题都只依赖于更小的子问题的求解。我们可以将问题的规模按照由大到小排列依次求解。每个子问题都只求解一次。


    2.自顶向上(备忘录)策略

    动态规划有一个性质为子问题重叠性质,就是对于子问题在递归过程中不断求解,虽然问题规模很小,但是求解次数会非常多,造成程序运行非常慢。在使用自顶向下的求解过程中,我们一般要设计一个备忘录,在递归求解过程中对于已经求解过的问题保存在备忘录中,当下次要使用时直接拿出来,不用再次求解。


    3.优缺点分析

    自顶向下只需要求解问题需要的解,不需要对所有子问题都去求解。但是它需要额外的递归开销。自底向上必须对所有子问题进行求解但是可有效减少计算时间和所需的存储空间。


    总结

    动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。解决动态规划问题的关键是找到最最优子结构并定义出递归式,根据经验,通常会分为若干种情况分开讨论,尤其注意容易遗漏的特殊情况(0、1、相等…)。在求解计算时,如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

     

    展开全文
  • 一般网站有哪些常见漏洞?

    千次阅读 2018-09-26 18:13:03
    随着互联网的广泛使用,Web应用已经融入到日常生活...在这些Web访问中,大多数应用不是静态的网页浏览,而是涉及到服务器侧的动态处理。此时,如果Java、PHP、ASP等程序语言的编程人员的安全意识不足,对程序参数输...
  • sql中常用的动态标签有哪些

    千次阅读 2018-09-21 08:30:04
    动态sql中常用的标签 If choose when otherwise trim where set foreach bind
  • jsp简介:
  • 常见的中间件有哪些

    万次阅读 2018-07-19 20:21:12
     Kafka使用Scala开发,而Scala又是JVM上运行的动态需要,因此对会Java的同学来说学习难度并不大,其客户端也支持Java语言,比较容易部署在本机上进行学习研究。 Facebook Thrift  Facebook Thrift是最新一代...
  • 理解动态规划 动态规划中递推式的求解方法不是动态规划的本质。 我曾经作为省队成员参加过NOI,保送之后也给学校参加NOIP的同学多次讲过动态规划,我试着讲一下我理解的动态规划,争取深入浅出。希望你看了我的答案...
  • 经常逛A站和B站的人,肯定对一个节目不陌生《网络上常见的GIF动态图》 今天就来分享一下,怎么通过爬虫自动的将这些个动作收藏到自己的电脑中(其实这个程序5月份就写好了,一直拖到现在才想起来将它分享出来)。 ...
  • Java两种动态代理JDK动态代理和CGLIB动态代理

    万次阅读 多人点赞 2018-08-07 15:33:35
    JDK动态代理 cglib动态代理 测试 代理模式 代理模式是23种设计模式的一种,他是指一个对象A通过持有另一个对象B,可以具有B同样的行为的模式。为了对外开放协议,B往往实现了一个接口,A也会去实现接口。但是B是...
  • 动态规划思想以及常见应用

    千次阅读 2018-03-30 18:30:52
    动态规划适合求解多阶段决策问题的最优解(可以简单理解为状态转换的阶段性问题)。这些问题必须满足最优化原理和子问题的无后向性。最优化原理:不管之前的决策是否最优,但是一定要保证从现在开始的决策是在之前...
  • linux查看静态库和动态有哪些函数

    千次阅读 2020-01-17 14:29:52
    查看静态库中有哪些函数 https://blog.csdn.net/tao546377318/article/details/51727696 nm -g -C --defined-only xxxx.a
  • 常见的DOM操作有哪些

    万次阅读 多人点赞 2019-05-16 14:51:59
    常见的DOM操作有哪些】 这里是修真院前端小课堂,每篇分享文从 【背景介绍】【知识剖析】【常见问题】【解决方案】【编码实战】【扩展思考】【更多讨论】【参考文献】 八个方面深度解析前端知识/技能,本篇...
  • js动态添加点击事件常见错误

    千次阅读 2017-09-20 00:24:18
    尤其是在动态的元素上添加点击事件。经常会添加之后没有反应。...这个问题可以在调试的窗口选中元素在监听事件中去查看没有添加上监听事件  如图:    就已经添加上了点击事件,如果没有。那么检查
  • Axure8实现最常见的左侧动态导航

    万次阅读 2018-03-23 02:34:52
    转载自:Axure8实现最常见的左侧动态导航当初自己想了很久才实现了这种左侧的动态菜单栏。今天我跟大家分享一下怎么实现点击实现动态开合的那种左侧菜单栏。希望能帮助到一些刚入门的朋友们。主要知识点:通过显示/...
  •  动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略  基本思想与分治...
  • 简单动态网站搭建

    万次阅读 多人点赞 2018-01-10 10:41:48
    1.静态网站动态网站的区别 2.掌握动态网站的不同的实现 3.在阿里云上如何搭建WordPress网站以及网站的管理和优化 静态网站:指全部由HTML代码格式页面组成的网站,所有内容包含在网页文件夹中。 主要用到...
  • Mybatis动态sql(有哪些)标签: 1、<if>: if是为了判断传入的值是否符合某种规则,比如是否不为空; 2、<where>: where标签可以用来做动态拼接查询条件,当和if标签配合的时候,不用显示的声明类...
  • 常见动态语言

    2009-04-24 13:10:00
    常见动态语言:D、JavaScript、ActionScript、Erlang、Groovy、Lisp、Lua、Objective-C、Perl、PHP、Python、Ruby、Scala、Smalltalk、Tcl、VBScript。
  • Mybatis常用的动态SQL标签有哪些

    千次阅读 2019-08-31 20:31:11
    适用于动态的包含where字句的一部分 if的特点是 当if的判断条件满足时,添加if标签中的字句 当if的判断条件不满足时,什么都不添加 choose: 适用于: 当判断的条件为true时,执行一个语句 当判断的条件为false时,...
  • 给定数组arr,arr中所有数都为正数,且不重复,每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个正整数aim代表要找的钱数,求换钱多少种方法? 这道题可以用暴力搜索,记忆搜索,动态规划,...
  • 静态网站动态网站的区别

    千次阅读 2019-08-29 17:37:55
    网页内容一经发布到网站服务器上,无论是否用户访问,每个静态网页的内容都是保存在网站服务器上的,也就是说,静态网页是实实在在保存在服务器上的文件,每个网页都是一个独立的文件; 静态网页的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 566,043
精华内容 226,417
关键字:

常见的动态网站有哪些