动态规划详细解释-蒲公英云

动态规划详细解释

推荐博客：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的时候钞票的最小张数。

$f(n)$ 只与 \[公式\] 相关；更确切地说：

\[公式\]

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 }