教你入门动态规划

· · 个人记录

动态规划VS搜索

动态规划，相信几乎所有人都听说过，但有些人不知道动态规划的好处，特别是没学过的人，经常把本该用动态规划做的题用搜索做，比如P1508和 P2607，导致 TLE，我当初也是这样。

为什么呢？因为搜索需要从一个状态开始，推出若干个决策，这若干个决策又会推出更多的决策，假设一个决策会推出2个决策：

次数 1 2 3 4 5 6 7 8 9 n
状态数 1 2 4 8 16 32 64 128 256 2的n次方

假设一个决策会推出10个决策时就更可怕了：

次数 1 2 3 4 5 6 7 8 9 n
状态数 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 10的n次方

所以搜索是一种时空消耗极大的算法，数据稍大时就有可能TLE或MLE，搜索优化？有一些效果，但还是会在超大数据时TLE或MLE。

相比之下，动态规划复杂度低，一般只有O(n的2次方或3次方），用我的实际举例子，搜索和动态规划算法整整因为时间原因整整差了60分。

动态规划入门

那，怎样学这种复杂度简单的算法呢？

追根溯源这个成语，我想大家一定听说过，没错，这也是动态规划的思想，从反方向找，往上赋最优值，直到赋到答案，输出它，与搜索的顺序完全相反。

现在，我建议先做P1002 P1216 P1508 这三道题。

P1002：

一道动规题，也是一道奥数题。

如上图，把在第一行和第一列的点都标上1（控制点及之后的不标记），之后的点是该交叉点上面和左面的和，转移方程:

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

代码： （抄了对你没好处）

#include<bits/stdc++.h>
using namespace std;
long long fi_x,fi_y,h_x,h_y,a[100][100];
bool b[100][100];
int main(){
    cin>>fi_x>>fi_y>>h_x>>h_y;
    b[h_x][h_y]=1;
    if(h_x-2>=0&&h_y-1>=0)b[h_x-2][h_y-1]=1;
    if(h_x-2>=0&&h_y+1<=fi_y)b[h_x-2][h_y+1]=1;
    if(h_x-1>=0&&h_y-2>=0)b[h_x-1][h_y-2]=1;
    if(h_x+1<=fi_x&&h_y-2>=0)b[h_x+1][h_y-2]=1; 
    if(h_x-1>=0&&h_y+2<=fi_y)b[h_x-1][h_y+2]=1;
    if(h_x+1<=fi_x&&h_y+2<=fi_y)b[h_x+1][h_y+2]=1;
    if(h_x+2<=fi_x&&h_y-1>=0)b[h_x+2][h_y-1]=1;
    if(h_x+2<=fi_x&&h_y+1<=fi_y)b[h_x+2][h_y+1]=1;
    for(int i=0;i<=fi_y;i++){
        if(b[0][i]==0)a[0][i]=1;
        else break;
    }
    for(int i=0;i<=fi_x;i++){
        if(b[i][0]==0)a[i][0]=1;
        else break;
    }  
    for(int i=1;i<=fi_x;i++){
        for(int j=1;j<=fi_y;j++){
            if(b[i][j]==0)a[i][j]=a[i-1][j]+a[i][j-1];
        }
    }
    cout<<a[fi_x][fi_y];

    return 0;
}

P1216： 当初我也找不出这道题的转移方程，此时我想出了我曾经在小学六年级时与同学玩的一种占卜游戏，可求得两者成为伴侣的关系： （一切真名用拼音首字母大写表示）

 C  R  Z  W  H  M
10 10 8  4  15  8
 0  2  4  11  7
  2  2  7  4
   0  5  3
    5  2
     3---------100%-3%=97%

 C  R  Z  Z  K  R
10 10 8  11  9 13
 0  2  3   2  4
  2  1  1  2
   1  0  1
    1  1
     0---------100%-0%=100%

我们先求出两个人名字每个字的笔画数，写在所对应字的下面，再在每两个数的下面的中间写上面两个数字差的的绝对值（就是大减小的差），得到最底下的一个数后，假设它为x吧，成为伴侣的概率便是100%-x%。

这种方法肯定是荒谬的，但如果你能把它理解成动态规划的转移图，那用处就大了，你的理解至少会减少几个小时。

但这道题的赋值方式与这种游戏有所不同，它不是求绝对值的差，而是求总和，要求下面两个值的最大值，并加上当前位置的值，理解也不难，附上转移方程和代码：

转移方程：

dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];

代码：（抄了对你没好处）

#include<bits/stdc++.h>
using namespace std;
int a[10000][10000],dp[10000][10000],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)cin>>a[i][j];
        }
    for(int i=1;i<=n;i++)dp[n][i]=a[n][i];
    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=i;j++)dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
        }
    cout<<dp[1][1];
    return 0;
    }

P1508:与上一题类似，但有几个注意点：

转移方程有所改动，尤其注意max函数只能输入两个数，三个数及以上就会编译错误 （当时我被卡了半天，以为编译器坏了） ：

dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i-1][j+1]))+a[i][j];

代码：（抄了对你没好处）

#include<bits/stdc++.h>
using namespace std;
int n,m,a[205][205],dp[205][205];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    for(int i=1;i<=n;i++)dp[1][i]=a[1][i];
    for(int i=2;i<=n+1;i++){
        for(int j=1;j<=m;j++)dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i-1][j+1]))+a[i][j];
    }
    cout<<dp[n+1][m/2+1];
    return 0;
}

这次的内容就结束了，运气好的话我还会出版背包dp的思考方法，祝大家过关斩将，AKIOI！