用ps如何做网站首页四川seo选哪家

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

 只与  相关；更确切地说：

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

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
//我要到哪里去”---push型的转移方程
int f[105],i,n,cost;
int main()
{
    scanf("%d",&n);
    f[0]=0;
    f[1]=1;
    for(i=0;i<=105;i++)
    f[i]=100000;
    f[0]=0;
    for(i=1;i<=n;i++)
    {
        int cost=100000;
        if(i>=1)  cost=min(cost,f[i-1]+1);
        if(i>=5)  cost=min(cost,f[i-5]+1);
        if(i>=11)  cost=min(cost,f[i-11]+1);
        f[i]=cost;
    }
    for(i=1;i<=n;i++)
        cout<<f[i]<<" ";
}

 

例题二：最长子序列

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
//求数组递增的最长子序列
int f[105],i,n,cost;
int main()
{
    int a[105];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i]=1;
    }

    for(int x=1;x<=n;x++)
    {
        for(int p=1;p<x;p++)
            if(a[p]<a[x])
            f[x]=max(f[x],f[p]+1);
        cout<<f[x]<<endl;
    }
    int ans=0;
    for(int x=1;x<=n;x++)
       ans=max(ans,f[x]);
    cout<<"max:"<<ans<<endl;
}

 

 

 

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

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
//我要到哪里去”---push型的转移方程
int f[105],i,n,cost;
int main()
{
    scanf("%d",&n);
    f[0]=0;
    f[1]=1;
   // memset(f,inf,sizeof(f));
   for(i=0;i<=105;i++)
    f[i]=100000;
     f[0]=0;
    f[1]=1;
    for(i=0;i<=n;i++)
    {
        f[i+1]=min(f[i+1],f[i]+1);
        f[i+5]=min(f[i+5],f[i]+1);
        f[i+11]=min(f[i+11],f[i]+1);
    }
    for(i=1;i<=n;i++)
        cout<<f[i]<<" ";
}