終於要學NOIP 以及NOI甚至IOI中最重要的部分了 動態規劃

首先要感謝ceeji神牛對我的無私幫助 幫我整理了好多資料讓我看 所以一定要加油了！

今天放的是The Gala的新歌 水手公園~ 「忘掉烦恼忘掉忧愁天空真晴朗」 ~

嗯 回到正題上來 動態規劃

首先對動態規劃要有個大面的了解

「动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。

這是來自維基百科的解釋

而 維基百科對於動態規劃 也有一個基本思想的定義：

「其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。」

首先我們來說下動態規劃裡面的術語

呃 還是結合例子來說方便點 看下面這個圖

這道題是求從A點到D點的最短路徑 應該是DP中最基礎的問題了 我們拿這道題來說

首先 作為動態規劃 要劃分階段 而且要保證 每個階段 無後效性 就是說 不管前面怎麼做 怎麼決策 都影響不到 後面的階段 這樣才能使用DP來做題

使用DP的最主要一點是 要保證到每一步的策略都是最優的 其實DP就是一種極度優化過的搜索 每一步都是搜索的終點又是搜索的起點 搜索的結果是每一步的最優的結果 然後再開始搜索的時候 用的是上一步的最优解来 进行搜索 这样就能保证到最后的结果就是整到题的最优解了

至於動態轉移方程 就是說 從第n步到第n+1步 到達下一個狀態 所需要經過的變化 動態轉移方程一般用偽代碼來表示

嗯 原理說道這裏 下面說說 最初級的幾道DP題目

數字三角形

７
３ ８
８ １ ０
２ ７ ４ ４
４ ５ ２ ６ ５

图示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。求出這個最大值。

• 每一步可沿左斜线向下或右斜线向下走；
• 1＜三角形行数≤100；
• 三角形中的数字为整数0，1，…99；

這道題 一般是作為DP的入門題目來看 呃 剛剛看完DP概念的時候 看著道題還是一丁點思路都沒有 不過這道題應該算是例題 後面給的有詳細的解析 看了看 基本明白要如何做

這道題有2個思路 一個是自上而下 一個是自下而上

先說說 自下而上的思路

用F[i,j]表示第i行第j個數到三角形最底層的最大數字和，即最優解，三角形最底層的最優解即為它本身,而第1層到第n-1層的最優解為 a[i+1][j]與a[i+1][j+1]的較大者與a[i][j]的和，依次從n-1層推導出最優解至第1層，最後f[0][0]即三角形的頂端的樹即為這道題的最優解。根據這個思路可以寫出來DP方程：

f[i,j]={
    f[i,j]=a[i,j]   (i=n),
    f[i,j]=f[i,j]+max(a[i+1,j],a[i+1,j+1])  (i<n)
}

即 通過求每個子問題中的最優解逐漸形成整個問題的最優解，主要思想就是逐步擴大成果。

代码如下

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
27
28
29

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
  int i,j,n;
  FILE *fin=fopen("input.txt","r");
  FILE *fout=fopen("out.txt","w");
  fscanf(fin,"%d",&n);
  int a[n][n],b[n][n];
  for(i=0;i<n;i++)
      for(j=0;j<=i;j++)
      {
          fscanf(fin,"%d",&a[i][j]);
          if(i==n-1)
              b[i][j]=a[i][j];
      }
  for(i=n-2;i>=0;i--)
      for(j=0;j<=i;j++)
      {
          if(b[i+1][j]>b[i+1][j+1])
              b[i][j]=a[i][j]+b[i+1][j];
          else
              b[i][j]=a[i][j]+b[i+1][j+1];
      }
  fprintf(fout,"%d",b[0][0]);
  return 0;
}

下面說說從頂層向下推的思路

/blog/uploads/2010/08/sjx2.png

其實和倒推的思路近似 每n+1層的數（不是末尾的）與第n層中的第j和j+1個數中的最大值相加 最後 到達最後一層 選擇最後一層中的最大值即為整個三角形的最優解

DP方程為

f[i,j]={
    f[i,j]=a[0,0],  (i=0,j=0)
    f[i,j]=f[i,j]+max(a[i-1,j],a[i-1][j+1]) (i>0)
}

恩 這樣就把這一道DP的入門題目解決了 通過這一題主要是爲了 學會寫動態轉移方程 以及感受DP的基本思想 而且 這道題可以通過兩種思路來 一種正推一種逆推 感覺逆推的方法更容易理解一些 但是 似乎並不是按照題目給的路子來走的 有時候換條路或許會比直著來更簡單 至於這個思路的代碼。。略了。。 恩 下面說說 我做的DP的第二題 網格中取數

给出一个N行M列（共有N×M个结点）的网格，左下角坐标为（1，1），右上角坐标（N，M），每个网格中有一个整数，从左下角开始只能沿着向上或向右的方向前进到下一个网格（如从（1，1）只能走到（1，2）或（2，1））。计算并输出从（1，1）出发，到（N，M）经过的数字的总和的最小值。

看这个例子 这是一个 5*7的 网格 里面随便填了几个数 要求是说 从 左下角的2开始 只能往向上或向右的方向走 求一个到6路径 并且这个路径所经过的数字之和最小

按照DP的思路来想 既然是求和最小的路径 那么最优解就是 数字之和最小的路径 每走一步即是一个阶段 只要保证每一个阶段走的路径数字和最小即可 这样我们可以写出 动态转移方程：

f[i,j]代表坐标[i,j]到达左下角的路径 经过的最小数字之和

f[i,j]={
    f[i,j]=a[i,j],  (i=n,j=1)
    f[i,j]=a[i,j]+f[i,j-1], (i=n,j>1)
    f[i,j]=a[i,j]+f[i+1,j], (i<n,j=1)
    f[i,j]=a[i,j]+min(f[i+1,j],f[i,j-1])    (i<n,j>1)
}

这样就能求出此问题的答案了

代码如下

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
  int i,j;
  FILE *fin=fopen("input.txt","r");
  FILE *fout=fopen("out.txt","w");
  int n,m;
  fscanf(fin,"%d %d",&n,&m);
  int num[n][m],b[n][m];
  for(i=0;i<n;i++)
      for(j=0;j<m;j++)
          fscanf(fin,"%d",&num[i][j]);
  b[n-1][0]=num[n-1][0];
  for(i=n-1;i>=0;i--)
      for(j=0;j<m;j++)
      {
          if(i==n-1&&j==0)  
              continue; 
          if(i==n-1)
          {
              b[i][j]=b[i][j-1]+num[i][j];
              continue;
          }
          if(j==0)
          {
              b[i][j]=b[i+1][j]+num[i][j];
              continue;
          }
          if(b[i+1][j]<b[i][j-1])
              b[i][j]=num[i][j]+b[i+1][j];
          else
              b[i][j]=num[i][j]+b[i][j-1];
      }
  fprintf(fout,"%d",b[0][m-1]);
  for(i=0;i<n;i++)
  {    for(j=0;j<m;j++)
          printf("%d ",b[i][j]);
      printf("\n");
  }
  return 0;
}

嗯 这一题也结束了 下面还是一个网格问题 和上一题很像 网格路线问题

给出一个N行M列（共有N×M个结点）的网格，左下角坐标为（1，1），右上角坐标（N，M），一个物体从左下角开始只能沿着向上或向右的方向前进到下一个结点（如从（1，1）只能走到（1，2）或（2，1））键盘输入N，M，计算并输出从（1，1）出发，到（N，M）共有多少条路径？

这一题 从 网格间换到了 网格的交点 既然是就路径 那我们按照DP思路来想 就是求每一步的 最优路径 但是这一题貌似看起来是没有什么最优情况 那就存能够到达这个点的 路径数目即可 由此可以写出DP方程：

f[i,j]代表从左下角到坐标为i,j的点的路径数目

f[i,j]={
    f[i,j]=0,   (i=n,j=0)
    f[i,j]=1,   (i=n或j=0)
    f[i,j]=f[i+1,j]+f[i,j+-]    (i<n,j>0)
}

根据这个动态转移方程 我们就能写出相应的程序 代码如下

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
27
28
29
30
31
32
33
34
35
36
37
38

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
  int i,j;
  FILE *fin=fopen("input.txt","r");
  FILE *fout=fopen("out.txt","w");
  int n,m;
  fscanf(fin,"%d %d",&n,&m);
  int b[n][m];
  b[n-1][0]=0;
  for(i=n-1;i>=0;i--)
      for(j=0;j<m;j++)
      {
          if(i==n-1&&j==0)  
              continue; 
          if(i==n-1)
          {
              b[i][j]=1;
              continue;
          }
          if(j==0)
          {
              b[i][j]=1;
              continue;
          }
          b[i][j]=b[i][j-1]+b[i+1][j];
      }
  fprintf(fout,"%d",b[0][m-1]);
  for(i=0;i<n;i++)
  {    for(j=0;j<m;j++)
          printf("%d ",b[i][j]);
      printf("\n");
  }
  return 0;
}

嗯 DP方面现在只做了这么多题目 都是很初级很初级的 只是算刚刚看到DP是个什么玩意儿= =至于真正的熟练应用 还差一大截 所以需要需要需要多多的练题 嗯

今天听常老师的课了 常老师说 NOIP中 还是以DP和搜索为重 所以说 这两样就是重点学习对象喽~ 加油！

话说这篇文章写了好长时间 一直在WP的草稿箱里面 = = 嗯 最后 由衷的感谢ceeji神牛对我的指导、どうもありがとうございます。