动态规划算法题总结

缺乏、安全感 2022-05-17 08:57 211阅读 0赞

# 一.动态规划的基本思想 #

> 动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过子结构重新构造最优解的过程很难统一。

在做这些题之前，没有接触过任何关于动态规划的概念，所以写的很吃力，很难过

下去了解了一些关于动态规划的概念,在此做个记录和总结

动态规划的基本模型:

*  确定问题的决策对象
 *  对决策问题划分阶段
 *  对各个阶段确定状态变量
 *  根据状态变量来确定费用函数和目标函数
 *  确定状态转移方程

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。并且保存子问题的解

动态规划是一种牺牲了空间，换取时间的算法.

--------------------

## 如何正确的理解动态规划算法？ ##

![这里写图片描述][70]

A * "1+1+1+1+1+1+1+1 =？" *
    
    A : "上面等式的值是多少"
    B : *计算* "8!"
    
    A *在上面等式的左边写上 "1+" *
    A : "此时等式的值为多少"
    B : *quickly* "9!"
    A : "你怎么这么快就知道答案了"
    A : "只要在8的基础上加1就行了"
    A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

动态规划算法是在记住每一步的最优解，从每一个子问题的最优解来推出整个问题的最优解

--------------------

动态规划 备忘录法：

*  动态规划的一种变形，使用自顶向下的策略，更像递归算法。
    
     *  初始化时表中填入一个特殊值表示待填入，当递归算法第一次遇到一个子问题时，计算并填表；以后每次遇到时只需返回以前填入的值。

动态规划 自底向上法:

*  这种方法一般需要恰当的定义子问题的”规模”概念，使得任何子问题的求解都执行依靠“更小的”子问题来解决，每个子问题只需要解决一次，在求解子问题的时候，应该确保你之前的更小的子问题已经求解成功

## 　　 ##

采用动态规划求解的问题需要具有两个特性：

> 最优子结构（Optimal Substructure）：问题的一个最优解中所包含的子问题的解也是最优的。  
> 重叠子问题（Overlapping Subproblems）：用递归算法对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。

问题具有最优子结构性质，我们才能写出最优解的递归方程；具有重叠子问题特性，我们才能通过避免重复计算来减少运行时间。

适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够的”小”,即问题的递归算法会反复地求绝相同的子问题，而不是一直生成新的子问题，一般来，如果可以用递归的方式求解相同的子问题，就称最优化问题具有重叠子问题.

综上所述，动态规划的关键是 —— 记忆，空间换时间，不重复求解，从较小问题解逐步决策，构造较大问题的解。

--------------------

举一个例子:求斐波拉契数列

Fibonacci (n) =1; n=0
    Fibonaci (n)=1 ; n=1;
    Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2);

大家都知道这个数列用递归来求解是十分方便的，在这里先使用递归解法

int fib(int n)
    {
       if(n<=0)
         return 0;
       if(n == 1)
         return 1;
        return fib(n-1)+fib(n-2);
    }

这种做法虽然很简单，但是它所使用的时间复杂度是指数的  
为什么会这样？  
![这里写图片描述][70 1]

在这个递归树中，可以清楚的看到很多节点被多次反复的执行，所以在时间上的开销是很大的，而动态规划为我们提供了一种新的方式，即把执行过的节点保存在表中，如果后面要实行的时候，查表就可以,

--------------------

## ①自顶向下的备忘录法 ##

备忘录法的概念在前面由所提及，在递归的过程中保存每个子问题的解，需要子问题的解，就检查有没有保存过这个解，直接返回

int Fibonacci(int n)
    {
              if(n<=0)
               return ;
               int Memo[n+1];
               for(int i == 0;i <=n;i++)
               {
                  Memo[i]=-1;
               }
            return fib(n,Memo);
    }
    int fib(int n,int Memo[])
    {
     if(Memo[n]!=-1)
         return Memo[n];
         //超出范围直接返回不然就保存
         if(n<=2)
             Memo[n]=1;
          else
              Memo[n]=fib(n-1,Memo)+fib(n-2,Memo);
    
           return Memo[n];
    }

## ②自底向上的动态规划 ##

带备忘的方法还是使用了递归，在这里我们可以换种想法，先计算子问题，再计算大问题

int fib(int n)
    {
            if(n<=0)
              return n;
              int Memo[n+1];
              Memo[0]=0；
              Memo[1]=1;
              for(i=2;i<=n;i++)
              {
                  Memo[i]=Memo[i-1]+Memo[i-2];
              }
              return Memo[n];
    }

使用这种方式也是利用数组现保存计算的值，通过观察参与循环的只有i,i-1,i-2项，因此该方法的空间也可以进一步的压缩

int fib(int n)
    {
           if(n<=1)
             return n;
           int fib_1=0;
           int fib_2=1;
           int fib_3=1;
           for(int i=2;i<=n;i++)
           {
                fib_3=fib_1+fib_2;
                fib_1=fib_2;
                fib_@=fib_3;
           }
    }

一般来说这两种方法所得到的算法具有相同的渐近时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归考察所有可能的子问题，由于没有频繁的递归函数的调用的开销，一般来说，自底向上的时间复杂度会比较抵

# 二.举例 #

A - 数字之塔  
Description  
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

![这里写图片描述][79b65092734d6a263a9280f5b332c5b9_v_1501552325]

Input  
输入数据首先包括一个整数C，表示数据的个数。  
每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间\[0,99\]内。  
Output  
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。  
Sample Input  
1  
5  
7  
3 8  
8 1 0  
2 7 4 4  
4 5 2 6 5  
Sample Output  
30

思路:求最大权值，由图可知从顶向下判断并不好判断，这个题可以采取自底向上法，根据求i-1层的最大值，求i-2层的最大值，以此类推，以解决子问题来解决整体的大问题.

//这道题应该是dp问题，可以从后往前推，得到最优化解
    #include<stdio.h>
    int main()
    {
       int tree[200][200],t,c,i,j;
       scanf("%d",&t);//有几组数据
       while(t--)//输入几组数据
       {
           scanf("%d",&c);//有几行
           for(i=1;i<=c;i++)
             for(j=1;j<=i;j++)
             {
                 scanf("%d",&tree[i][j]);//输入数塔的内容
             }
    
             for(i=c-1;i>=1;i--)//从下向上
              for(j=1;j<=i;j++)
              {   //c-1层的最大值。。。。然后递归
                  if(tree[i+1][j]<tree[i+1][j+1])
                     tree[i][j]+=tree[i+1][j+1];
                     else
                     tree[i][j]+=tree[i+1][j];
              }
              printf("%d\n",tree[i+1][j-1]);//输出最高一层的数值
       }
        return 0;
    }

B - 兑换硬币  
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。  
Input  
每行只有一个正整数N，N小于32768。  
Output  
对应每个输入，输出兑换方法数。  
Sample Input  
2934  
12553  
Sample Output  
718831  
13137761

思路：一开始的想法是通过暴力枚举来求值，但是通过查看样例，使用暴力枚举一定会超时，于是联想到最近在学的dp问题，因为它是有多个类似的子问题来组成的  
有一枚硬币是一个 dp\[1\]=1;  
两块钱也是一种情况 dp\[2\]=dp\[2-1\]+1;  
三块也是一种情况 dp\[3\]=dp\[3-1\]+dp\[3-2\]+dp\[3-3\]=3 ;  
四块也是一种情况 dp\[4\]=dp\[4-3\]+dp\[4-2\]+do\[4-1\]=4;  
以此类推

dp\[n\]=dp\[j\]+dp\[j-i\]

#include<stdio.h>
    #include<string.h>
    int main()
    {
        int n,i=1,j;
        int count[32876];
        while(scanf("%d",&n)==1)
        {
            memset(count,0,sizeof(count));
            count[0]=1;
            i=1;
           while(i<=3)
           {
                 for(j=i;j<=n;j++)
             {
                 count[j]+=count[j-i];
             }
             i++;
           }
           printf("%d\n",count[n]);
        }
    }

C - 超级跳跃  
Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.

The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path.  
Your task is to output the maximum value according to the given chessmen list.  
Input  
Input contains multiple test cases. Each test case is described in a line as follow:  
N value\_1 value\_2 …value\_N  
It is guarantied that N is not more than 1000 and all value\_i are in the range of 32-int.  
A test case starting with 0 terminates the input and this test case is not to be processed.  
Output  
For each case, print the maximum according to rules, and one line one case.  
Sample Input  
3 1 3 2  
4 1 2 3 4  
4 3 3 2 1  
0  
Sample Output  
4  
10  
3

思路：这个题相当于求递增序列。。。。。。。。选择超级跳跃的时候，也就是递增序列的最后一位  
对于递增序列的动态规划方程  
do\[i\]=a\[i\]+dp\[j\]; dp\[j\]表示之前的序列递增的值

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    int main()
    {
        int n,i,j;
        int a[1000];
        int dp[1000],sum=0;
        while(scanf("%d",&n)&&n)
        {
             memset(a,0,sizeof(a));
             memset(dp,0,sizeof(dp));
              for(i=1;i<=n;i++)
              {
                  scanf("%d",&a[i]);//输入内容
              }
              dp[0]=a[0];
              sum=0;
             for(i=1;i<=n;i++)
             {
                dp[i]=a[i];//刷新dp[i]
                for(j=0;j<i;j++)
                {
                    if(a[i]>a[j])
                    {
                       if(dp[i]<a[i]+dp[j])
                       dp[i]=a[i]+dp[j];//条件诗
                    }
                }
                if(sum<dp[i])
                sum=dp[i];//使用sum存储每个递增序列的值
             }
             printf("%d\n",sum);
        }
        return 0;
    }

D - 超级跳跃 Again

A numeric sequence of ai is ordered if a1 < a2 < … < aN. Let the subsequence of the given numeric sequence ( a1, a2, …, aN) be any sequence ( ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.  
Input  
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000  
Output  
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.  
Sample Input  
7  
1 7 3 5 9 4 8  
Sample Output  
4

思路:这道题是求最长的递增序列，但是需要注意的一点就是每次跳跃的值不能小于上次跳跃的值，再样例中不能经过9  
在这里通过i 和i-1的对比，如果是递增的，就保存再dp\[\]中，将所有能到达终点的路径保存下，求最大

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    int fun(int a[],int n)
    {
        if(n==1)
        return 1;
        int dp[1005];
        int i=0,j=1,sum=0;
        memset(dp,0,sizeof(dp));
        dp[0]=1;
           for(i=1;i<=n;i++)
          {
              sum=0;
              for(j=0;j<i;j++)
             {
                   if(a[i]>a[j])
                   {
                       if(sum<dp[j])
                       sum = dp[j];
                   }   
             }
             dp[i]=sum+1;//还有本身的区域,所以要加1
          }
          sum=0;
        for(i=1;i<=n;i++)
        {
             if(sum<dp[i])
             sum=dp[i];
        }
            return sum;
    }
    int main()
    {
        int n,i;
        int a[1005];
        while(scanf("%d",&n)!=EOF)
        {
          memset(a,0,sizeof(a));
          for(i=0;i<n;i++)
           scanf("%d",&a[i]);
           printf("%d\n",fun(a,n));
        }
        return 0;
    }

E - 超级跳跃 Remake

atMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he’s going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse – after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.  
Input  
There are several test cases. Each test case consists of

a line containing two integers between 1 and 100: n and k  
n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) … (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), … (1,n-1), and so on.  
The input ends with a pair of -1’s.  
Output  
For each test case output in a line the single integer giving the number of blocks of cheese collected.

思路：这道题是dfs算法和dp进行结合，也可以理解为即记忆化搜索  
dp部分还是求整体的递增序列,只不过增加了多行数据  
通过dfs遍历，使用一个变量，将每一行的递增序列保存

使用 dp \[x\] \[y\] =dp1+a\[x\]\[y\];

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int N, M ;//迷宫大小和每次能走的路径
    int a[105][105];//储存地图
    int dp[105][105];
    int next[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1};//这道题可以走四个方向
    int dfs(int x, int y)
    {
        if (dp[x][y])//如果记录过
            return dp[x][y];返回上层
        int i, tx, ty, k;
        int dp1 = 0;
        for (i = 1; i <= M; i++)//控制M，tmp会不断刷新
        {
            for (k = 0; k < 4; k++)
            {
                tx = x + next[k][0] * i;//四个方向
                ty = y + next[k][1] * i;
                if (tx < 1 || tx > N || ty < 1 || ty > N)//边界条件
                    continue;
                if (a[tx][ty] > a[x][y])
                {
                    int tmp = dfs(tx,ty);
                    if (dp1 < tmp)
                        dp1 = tmp ;
                }
            }
        }
        dp[x][y] = dp1 + a[x][y];//递增序列
        return dp[x][y];
    }
    int main()
    {
        int i, j;
        while (scanf("%d %d", &N, &M) != EOF)
        {
            memset(dp, 0, sizeof(dp));
            memset(a, 0, sizeof(a));
            if (M == -1 && N == -1)
                break;
            for (j = 1; j <= N; j++)
                for (i = 1; i <= N; i++)
                    scanf("%d", &a[j][i]);
            printf("%d\n",dfs(1, 1));
        }
        return 0;
    }

F - 超级跳跃 2  
esus, what a great movie! Thousands of people are rushing to the cinema. However, this is really a tuff time for Joe who sells the film tickets. He is wandering when could he go back home as early as possible.  
A good approach, reducing the total time of tickets selling, is let adjacent people buy tickets together. As the restriction of the Ticket Seller Machine, Joe can sell a single ticket or two adjacent tickets at a time.  
Since you are the great JESUS, you know exactly how much time needed for every person to buy a single ticket or two tickets for him/her. Could you so kind to tell poor Joe at what time could he go back home as early as possible? If so, I guess Joe would full of appreciation for your help.  
Input  
There are N(1<=N<=10) different scenarios, each scenario consists of 3 lines:  
1) An integer K(1<=K<=2000) representing the total number of people;  
2) K integer numbers(0s<=Si<=25s) representing the time consumed to buy a ticket for each person;  
3) (K-1) integer numbers(0s<=Di<=50s) representing the time needed for two adjacent people to buy two tickets together.  
Output  
For every scenario, please tell Joe at what time could he go back home as early as possible. Every day Joe started his work at 08:00:00 am. The format of time is HH:MM:SS am|pm.  
Sample Input  
2  
2  
20 25  
40  
1  
8  
Sample Output  
08:00:40 am  
08:00:08 am

思路:注意这道题的12:00属于pm,我是求出全部所需要的秒数之后然后转化为时间,  
还有题目所给予的一列数并不是递增的  
动态规划方程  
第i个人单独买票  
或则和第i和i-1个人一起麦片  
可列方程 MAX=\{(dp\[i-1\]+everytime\[i\],dp\[i-2\]+secondtime\[i\])  
有三种情况  
第一种就是只有一个人，单独买票  
dp\[0\]=erverytime\[0\]  
第二种有两个人  
需要判断分开买票时间短还是一起买时间短  
第三种根据动态规划方程可列

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    struct time
    {
        int hour;
        int mintues;
        int seconds;
    };
    struct time atime;
    int main(void)
    {
        int n,N,i,j;
        int firsttime;
        int erverytime[2005],sceondtime[2005],dp[2005];
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d",&N);
            atime.hour=8;
            atime.mintues=0;
            atime.seconds=0;
            for(i=0;i<N;i++)
            {
                scanf("%d",&erverytime[i]);
            }
            for(i=1;i<N;i++)
            {
             scanf("%d",&sceondtime[i]);
            }
            memset(dp,0,sizeof(dp));
            for(i=0;i<N;i++)
            {
                if(i == 0)
                dp[0]=erverytime[0];
                 if(i == 1)
                 {
                     if(erverytime[0]+erverytime[1]<sceondtime[1])
                     dp[1]=erverytime[0]+erverytime[1];
                     else
                     dp[1]=sceondtime[1];
                 }
                 if(i>=2)
                 {
                    if(dp[i-1]+erverytime[i]<dp[i-2]+sceondtime[i]) 
                     dp[i]=dp[i-1]+erverytime[i];
                  else
                     dp[i]=dp[i-2]+sceondtime[i];
                 }  
            } 
            sceondtime[N]=dp[i-1];
            atime.seconds=(sceondtime[N]%3600)%60;
            atime.mintues=sceondtime[N]%3600/60;
            atime.hour=8+(sceondtime[N]/3600);
            if(atime.hour < 12)
            {   if(atime.hour<10)
                printf("0");
                printf("%d:",atime.hour);
                if(atime.mintues<10)
                printf("0");
                printf("%d:",atime.mintues);
                if(atime.seconds<10)
                printf("0");
                printf("%d am\n",atime.seconds);
            }
            else
            {
                printf("%d:",atime.hour);
                if(atime.mintues<10)
                printf("0");
                printf("%d:",atime.mintues);
                if(atime.seconds<10)
                printf("0");
                printf("%d pm\n",atime.seconds);
            }  
        }
        return 0;
    }

[70]: /images/20220517/2bd4ce93aa224b8e991569b753f5cbe7.png
[70 1]: /images/20220517/94564bb7f61647809d91ff52fe890564.png
[79b65092734d6a263a9280f5b332c5b9_v_1501552325]: https://odzkskevi.qnssl.com/79b65092734d6a263a9280f5b332c5b9?v=1501552325