动态规划总结

      ---恢复内容开始---

      动态规划来源于分治法,本质是为了节省递归栈所消耗的时间/空间,同时把相同的子问题的解记录下来,防止系统做重复工作,浪费时间。

      一般用动态规划做题时候,要从分治法开始,进一步考虑是否存在相同的子问题解且解是否重复,如果有可以采用动态规划求解【当然递归方程还是要写的】。

      动态规划的递归方程和分治法略有不同,动态规划的递归一般都用二维数组储存数据【当然也有用一维数组甚至一个变量的,不过都是二维数组的简化版】,首先我们要弄清楚m[i][j]的几何意义,然后根据题目要求写出m[i][j]=...【一般都是和m其他元素挂钩的】,这就是动态规划的递归方程。

      一般写递归方程分为以下几种情况

      1.确定规划起点终点,规划方向确定

      例题:

      7-1 数字三角形 (30 分)
       

      给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下),使该路径经过的数字总和最大。

      QQ截图20170929023616.jpg

      输入格式:

      输入有n+1行:

      第 1 行是数字三角形的行数 n,1<=n<=100。

      接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。

      输出格式:

      输出最大路径的值。

      输入样例:

      在这里给出一组输入。例如:

      5 
      7 
      3 8 
      8 1 0 
      2 7 4 4
      4 5 2 6 5

      输出样例:

      在这里给出相应的输出。例如:

      30

      一般遇到这种题只需要从终点入手,就会发现到终点的路径值只能是m[i-1][j]或者m[i-1][j-1]再加自己的值,这样子到终点问题就被转化成为了到达倒数第二层格子的值,以此类推。

      #include<iostream>
      using namespace std;
      
      int main()
      {
          int n,i,j;
          cin>>n;
          int a[101][101];
          int d[101][101];
          for(i=1;i<101;i++)
          {
              for(j=1;j<101;j++)
              {
                  a[i][j]=0;
              }
          }
          for(i=1;i<=n;i++)
          {
              for(j=1;j<=i;j++)
              {
                  cin>>a[i][j];
              }
          }
      
          for(j=1;j<=n;j++)
          {
              d[n][j]=a[n][j];
          }
          for(i=n-1;i>=1;i--)
          {
              for(j=1;j<=n;j++)
              {
                  if(d[i+1][j]>d[i+1][j+1])
                  {
                      d[i][j]=d[i+1][j]+a[i][j];
                  }
                  else
                  {
                      d[i][j]=d[i+1][j+1]+a[i][j];
                  }
              }
          }
          cout<<d[1][1];
      }

      当然不创建d数组而直接覆盖a数组也是可以的

      结论:这种确定方向的题,从终点把每个情况想清楚,然后得出最大最小即可。

      其他问题:商人过路费,求子段最小操作数问题

      2.方向不确定或者自由,起终点确定:

      3-2 租用游艇问题 (22 分)
       

      题目来源:王晓东,《算法设计与分析》

      长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法,计算出从游艇出租站1 到游艇出租站n所需的最少租金。

      输入格式:

      第1 行中有1 个正整数n(n<=200),表示有n个游艇出租站。接下来的第1到第n-1 行,第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金。

      输出格式:

      输出从游艇出租站1 到游艇出租站n所需的最少租金。

      输入样例:

      在这里给出一组输入。例如:

      3
      5 15
      7

      输出样例:

      在这里给出相应的输出。例如:

      12

      这道题同样从终点想到起点,从i到n,要么直接过去,要么经过一堆中途站,而这些中途站所在值可以作为子问题求解。

      递归方程:m[i][j]从第i个站出发到j=max(m[i][k]+m[k][j],m[i][j])其中k<n,大于y一般都用for循环求出结果。

      #include<iostream>
      using namespace std;
      int main()
      {
          int n,i,j,k;
          int yangtzeriver[200][200];
          cin>>n;
          for(i=0;i<n;i++)
          {
              yangtzeriver[i][i]=0;
              
          }
          for(i=0;i<n;i++)
          {
              for(j=i+1;j<n;j++)
              {
                  cin>>yangtzeriver[i][j];
                  
              }
          }
          //cout<<"e";
          for(i=n-1;i>=0;i--)
          {
              //cout<<" d";
              for(j=i+1;j<n;j++)
              {
                  //cout<<yangtzeriver[i][j]<<" "<<(yangtzeriver[i][j-1]+yangtzeriver[j-1][j]);
                  
                  int mini=min(yangtzeriver[i][j],yangtzeriver[i][j-1]+yangtzeriver[j-1][j]);
                  for(k=i+1;k<j;k++)
                  {
                      int q=min(yangtzeriver[i][j],yangtzeriver[i][k]+yangtzeriver[k][j]);
                      //cout<<yangtzeriver[i][j]<<" "<<(yangtzeriver[i][k]+yangtzeriver[k][j])<<" ";
                      if(q<mini)
                      {
                          mini=q;
                      }
                  }
                  //cout<<mini;
                  yangtzeriver[i][j]=mini;
              }
          }
          cout<<yangtzeriver[0][n-1];

      如:3-1,3-3

      3.方向确定,起终点不自由

      一般采用方法是记录最大值

      如:

      3-2 租用游艇问题 (22 分)
       

      题目来源:王晓东,《算法设计与分析》

      长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法,计算出从游艇出租站1 到游艇出租站n所需的最少租金。

      输入格式:

      第1 行中有1 个正整数n(n<=200),表示有n个游艇出租站。接下来的第1到第n-1 行,第i行表示第i站到第i+1站,第i+2站, ... , 第n站的租金。

      输出格式:

      输出从游艇出租站1 到游艇出租站n所需的最少租金。

      输入样例:

      在这里给出一组输入。例如:

      3
      5 15
      7

      输出样例:

      在这里给出相应的输出。例如:12

      一般遇到这种题,就不要把思维局限在终点。要这样想:从任意一个数开始,如果前面一堆数<0,
      那以他为底的尾串就是自己,否则是前面一堆数加上这个数得到递归方程m[j]=max(m[j-1]+num[j],num[j]),
      或者if num[j]<0,m[j]=num[j],else m[j]=(m[j-1]+num[j])
      代码省略 自己看书
      //看书
       
            
      (当然 直接分治法方法加备忘录 也是可以的)

      4.都没有 自己挑 如0-1背包
      0-1背包:给定种物品和一个容量为的背包,物品的重量是,其价值为,背包问题是如何使选择装入背包内的物品,使得装入背包中的物品的总价值最大。其中,每种物品只有全部装入背包或不装入背包两种选择。
      这种题目二维数组的代表意义会十分的奇怪,比如说在0-1背包中,一个数代表从几号物品开始装,另一个数代表容量。
      把二维数组顺序搞明白后,就会明显发现m[i][j]=max(m[i+1][j-i的价值],m[i+1][j])【前提:能装的下(j>i的价值),装不下直接m[i+1][j]】
      然后把最后一行填好,就能往上填表了


      #include<iostream>
      using namespace std;
      int main()
      {
          int n,capity,i,j;
          cin>>n>>capity;
          int item[100],percapity[100];
          for(i=0;i<n;i++)
          {
              cin>>item[i];
              cin>>percapity[i];
          }
          int bag[100][100];
          for(j=0;j<=capity;j++)
          {
              if(j<percapity[n-1])
              {
                  bag[n-1][j]=0;
              }
              else bag[n-1][j]=percapity[n-1];
          }
          for(i=n-2;i>=0;i--)
          {
              for(j=1;j<=capity;j++)
              {
                  if(j>=percapity[i])
                  {
                      bag[i][j]=max(bag[i+1][j],bag[i+1][j-percapity[i]]+item[i]);
                  }
                  else bag[i][j]=bag[i+1][j];
              }
          }
          cout<<bag[0][capity];
      }
       
            

      一般情况下,我们可以根据表之前的结果得到m[i][j]的结果,通常需要比较i,j和递归式里面i,j的关系,从而得到i和j在填表for循环里面的顺序,从而求i和j究竟递增,还是递增。一般递归式里面i比原i大递减,否则递增,j同理。

      相关文章
      相关标签/搜索
      每日一句
        每一个你不满意的现在,都有一个你没有努力的曾经。
      公众号推荐
         一个历史类的公众号,欢迎关注
      一两拨千金
      今期管家婆大图 玄机图香港挂牌正版彩图六合彩资料大全香港马会资料白小姐中特玄机香港挂牌之全篇