动态规划详细解释

Love The Way You Lie 2023-08-17 16:26 132阅读 0赞

推荐博客：[https://www.zhihu.com/question/23995189/answer/613096905][https_www.zhihu.com_question_23995189_answer_613096905]

**【动态规划满足的条件】**

**最优子结构性质：**大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。

**无后效性：**一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。

要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。

**“未来与过去无关”，**这就是**无后效性**。（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）

**【如何设计DP算法】**

下面介绍比较通用的设计DP算法的步骤。

首先，把我们面对的**局面**表示为x。这一步称为**设计状态**。对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).

**       找出f(x)与哪些局面有关（记为p）**，写出一个式子（称为**状态转移方程**），通过f(p)来推出f(x).

【DP三连】

设计DP算法，往往可以遵循DP三连：

我是谁？ ——设计状态，表示局面  
　　我从哪里来？  
　　我要到哪里去？ ——设计转移

设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，**更新能从x走到的一些解**。这种DP也是不少的，我们以后会遇到。

总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。

**例题讲解：换硬币**

如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出w的时候钞票的最小张数。

![\[公式\]][equation_tex_f_28n_29] 只与 ![\[公式\]][equation_tex_f_28n-1_29_2Cf_28n-5_29_2Cf_28n-11_29] 相关；更确切地说：

![\[公式\]][equation_tex_f_28n_29_3D_5Cmin_5C_7Bf_28n-1_29_2Cf_28n-5_29_2Cf_28n-11_29_5C_7D_2B1]

pull型的转移方程：我从哪里来

1 #include<cstdio>
     2 #include<iostream>
     3 #include<algorithm>
     4 using namespace std;
     5 //我要到哪里去”---push型的转移方程
     6 int f[105],i,n,cost;
     7 int main()
     8 {
     9     scanf("%d",&n);
    10     f[0]=0;
    11     f[1]=1;
    12     for(i=0;i<=105;i++)
    13     f[i]=100000;
    14     f[0]=0;
    15     for(i=1;i<=n;i++)
    16     {
    17         int cost=100000;
    18         if(i>=1)  cost=min(cost,f[i-1]+1);
    19         if(i>=5)  cost=min(cost,f[i-5]+1);
    20         if(i>=11)  cost=min(cost,f[i-11]+1);
    21         f[i]=cost;
    22     }
    23     for(i=1;i<=n;i++)
    24         cout<<f[i]<<" ";
    25 }

例题二：最长子序列

1 #include<cstdio>
     2 #include<iostream>
     3 #include<algorithm>
     4 using namespace std;
     5 //求数组递增的最长子序列
     6 int f[105],i,n,cost;
     7 int main()
     8 {
     9     int a[105];
    10     scanf("%d",&n);
    11     for(int i=1;i<=n;i++)
    12     {
    13         scanf("%d",&a[i]);
    14         f[i]=1;
    15     }
    16 
    17     for(int x=1;x<=n;x++)
    18     {
    19         for(int p=1;p<x;p++)
    20             if(a[p]<a[x])
    21             f[x]=max(f[x],f[p]+1);
    22         cout<<f[x]<<endl;
    23     }
    24     int ans=0;
    25     for(int x=1;x<=n;x++)
    26        ans=max(ans,f[x]);
    27     cout<<"max:"<<ans<<endl;
    28 }

push型的转移方程：我要到哪里去

1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<queue>
     6 #define inf 0x3f3f3f3f
     7 using namespace std;
     8 //我要到哪里去”---push型的转移方程
     9 int f[105],i,n,cost;
    10 int main()
    11 {
    12     scanf("%d",&n);
    13     f[0]=0;
    14     f[1]=1;
    15    // memset(f,inf,sizeof(f));
    16    for(i=0;i<=105;i++)
    17     f[i]=100000;
    18      f[0]=0;
    19     f[1]=1;
    20     for(i=0;i<=n;i++)
    21     {
    22         f[i+1]=min(f[i+1],f[i]+1);
    23         f[i+5]=min(f[i+5],f[i]+1);
    24         f[i+11]=min(f[i+11],f[i]+1);
    25     }
    26     for(i=1;i<=n;i++)
    27         cout<<f[i]<<" ";
    28 }

转载于:https://www.cnblogs.com/Aiahtwo/p/11305320.html

[https_www.zhihu.com_question_23995189_answer_613096905]: https://www.zhihu.com/question/23995189/answer/613096905
[equation_tex_f_28n_29]: https://www.zhihu.com/equation?tex=f%28n%29
[equation_tex_f_28n-1_29_2Cf_28n-5_29_2Cf_28n-11_29]: /images/20230810/629e697518fe4bc792c3573ac9cda00e.png
[equation_tex_f_28n_29_3D_5Cmin_5C_7Bf_28n-1_29_2Cf_28n-5_29_2Cf_28n-11_29_5C_7D_2B1]: /images/20230810/caaf99e3beb74655bacabecdb3aacad8.png