2016-02-11

动态规划基础(复习)

文章目录

原文地址:https://ngunauj.github.io

菲波那西数列
记忆化搜索写法(递归)

#include<iostream>    
#include<string.h>  
using namespace std;    
int dp[50];  
int f(int i){  
    if(dp[i]!=-1)return dp[i];  
    else return dp[i]=f(i-1)+f(i-2);  
}  
int main(){  
    int n;  
    while(cin>>n){  
            memset(dp,-1,sizeof dp);  
            dp[0]=1;dp[1]=1;  
            cout<<f(n)<<endl;  
    }  
    return 0;  
}

递推写法

/* ***********************************************
Author        :guanjun
Created Time  :2016/2/11 9:23:02    
File Name     :1.cpp
************************************************ */
#include<iostream>
using namespace std;
int main(){
    int n;
    int dp[50];
    dp[1]=dp[0]=1;
    while(cin>>n){
        if(n<=1)cout<<1<<endl;
        else{   
            for(int i=2;i<=n;i++){
                dp[i]=dp[i-1]+dp[i-2];
            }
            cout<<dp[n]<<endl;
        }
    }
    return 0;
}

其中，用数组将已经计算过的数据存储起来在下次计算的时候直接拿出来用，避免重复的运算，去掉重复的搜索树。这样的过程就叫做记忆化搜索。（上面的递归写法）
例题1:走楼梯问题
有一人要爬n阶的楼梯，他一次可以爬1阶或2阶，问要爬完这n阶楼梯，共有多少种方法？
设f[i]表示走到第i阶有几种方法。则f[i]=f[i-1]+f[i-2] f[1]=1;f[2]=2;

动态规划原理

分类加法原理分步乘法原理

例题2:最长不下降子序列问题
例如，下列数列
13 7 9 16 38 24 37 18 44 19 21 22 63 15的最长不下降子序列为
7 9 16 18 19 21 22 63 长度为8
设f[i]表示前i个数能得到的最长的子序列的长度。f[i]=max(f[j]+1) j<i且a[j]<=a[i]
/ **
Author :guanjun
Created Time :2016/2/11 10:29:33
File Name :1.cpp
** */

#include <iostream>
#include <string.h>
using namespace std;
int main()
{
    int a[100],dp[100];
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>a[i];
        int len=-1;
        for(int i=1;i<=n;i++){
            dp[i]=1;
            for(int j=1;j<i;j++){
                if(a[i]>=a[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
                len=max(dp[i],len);
            }
        }
        cout<<len<<endl;
    }
    return 0;
}

例题3:数字三角形
dp[i,j]=max(dp[i-1,j],dp[i-1,j-1])+a[i,j]
动态规划的定义
动态规划是解决多阶段**决策过程最优化问题的一种方法。
阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。
状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。
决策：从某阶段的一个状态演变到下一个阶段某状态的选择。
状态转移方程:
前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由i阶段到i+1阶段状态的演变规律，称为状态转移方程。
形如：
f[i] = f[i - 1]+ f[i - 2]
f[i,j]=max(f[i-1,j],f[i-1,j-1])+a[i,j]等等
动态规划适用的基本条件——具有相同子问题
首先，我们必须要保证这个问题能够分解出几个子问题，并且能够通过这些子问题来解决这个问题。
其次，将这些子问题做为一个新的问题，它也能分解成为相同的子问题进行求解。
也就是说，假设我们一个问题被分解为了A,B,C三个部分，那么这A,B,C分别也能被分解为A,B,C三个部分，而不能是D,E,F三个部分。
动态规划适用的基本条件——满足最优子结构
问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。

动态规划适用的基本条件——满足无后效性
“过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内涵
这是动态规划中极为重要的一点，如果当前问题的具体决策，会对解决其它未来的问题产生影响，如果产生影响，就无法保证决策的最优性.

例4:最大子序列和
题意：给你一个有正有负的序列，求一个最长的连续子序列，使其和最大！
样例输入： -5 6 -1 5 4 -7
样例输出： 14
设dp[i]为到第i个数能得到的最大和。那么
if(dp[i-1]<0)dp[i]=a[i];
else dp[i]=dp[i-1]+a[i];

/* ***********************************************
Author        :guanjun
Created Time  :2016/2/11 10:29:33
File Name     :1.cpp
************************************************ */
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
    int a[100],dp[100]; 
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>a[i];
        memset(dp,0,sizeof dp);
        int Max=-1;
        for(int i=1;i<=n;i++){  
            if(dp[i-1]<0)dp[i]=a[i];
            else dp[i]=dp[i-1]+a[i];
            Max=max(Max,dp[i]);
        }
        cout<<Max<<endl;
    }
    return 0;
}

动态规划更加实用的一般步骤:
1.确定状态：
（一维描述不完就二维，二维不行就三维四维……总之要敢想）
状态的参数一般有
1）描述位置的：前(后)i单位，第i到第j单位，坐标为(i,j)等
2）描述数量的：取i个，不超过i个，至少i个等
3）描述对后有影响的：状态压缩的，一些特殊的性质

2.确定转移方程：
1）检查参数是否足够；
2）分情况：最后一次操作的方式，取不取，怎么样放，前一项是什么
3）初始边界是什么。
4）注意无后效性。比如说，求A就要求Ｂ，求Ｂ就要求Ｃ，而求Ｃ就要求Ａ，这就不符合无后效性了。
技巧：根据状态枚举最后一次决策（即当前状态怎么来的）就可确定出状态转移方程！

3.确定编程实现方式
1）递推
2）记忆化搜索
凡是可以递推的均可以用记忆化搜索，
但是有的问题却只能用记忆化搜索解决！
例5:滑雪（poj1088）
Michael喜欢滑雪，这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1　2　3　4　5
16 17 18 19　6
15 24 25 20　7
14 23 22 21　8
13 12 11 10　9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。　
第一步：确定状态
f[i][j]表示从（i，j）滑下的最长路径长度
第二步：确定状态转移方程
——由于f[i][j]由上下左右四个方向转移过来
F[i][j] = max {f[i - 1][j] + 1(a[i - 1][j] <a[i][j])
　　　　　{f[i + 1][j] + 1(a[i + 1][j] <a[i][j])
　　　　　{f[i][j - 1] + 1 (a[i][j - 1] <a[i][j])
　　　　　{f[i][j + 1] + 1(a[i][j + 1] <a[i][j])
（初值）：f[i][j] = 0
第三步：确定实现方法
相信同学们已经看出问题了，我们没法通过递推的方式在算f[i][j]之前将他上下左右四个点的值都求出来。
所以记忆化搜索就成为解决这个问题的唯一办法！

/* ***********************************************
Author:guanjun
Created Time  :2016/2/11 10:29:33
File Name :1.cpp
************************************************ */
#include <iostream>
#include <string.h>
using namespace std;
int dp[110][110];
int a[110][110];
int n,m;
int dfs(int x,int y){
    if(dp[x][y]!=-1)return dp[x][y];
    dp[x][y]=1;
    if((a[x-1][y]<a[x][y])&&(x>1))dp[x][y]=max(dp[x][y],dfs(x-1,y)+1);
    if((a[x+1][y]<a[x][y])&&(x<n))dp[x][y]=max(dp[x][y],dfs(x+1,y)+1);
    if((a[x][y-1]<a[x][y])&&(y>1))dp[x][y]=max(dp[x][y],dfs(x,y-1)+1);
    if((a[x][y+1]<a[x][y])&&(y<n))dp[x][y]=max(dp[x][y],dfs(x,y+1)+1);
    return dp[x][y];
}
int main()
{
    while(cin>>n>>m){
        memset(dp,-1,sizeof dp);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        }
        int Max=-1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                Max=max(Max,dfs(i,j));
            }
        cout<<Max<<endl;
    }
return 0;
}

例6：最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。
给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
最长公共子序列:公共子序列中长度最长的子序列。
给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn}，找出X和Y的一个最长公共子序列。
样例输入:
abcfbc
abfcab
样例输出：4
第一步：确定状态
f[i][j]表示前一个字符串的前i位与后一个字符串的前j位的最长公共子序列长度
第二步：确定状态转移方程
当x[i]==y[j]，长度为i的子序列和长度为j的子序列的最长公共子序列就是长度为i-1和长度为j-1 的子序列中最长的公共子序列加上1
即：f[i][j]=f[i-1][j-1]+1
当x[i]!=x[j]，第一个序列长度为i的子序列和第二个序列中长度为j的子序列的公共子序列中x[i]和y[j]不同时出现。
也就是说在x[0]~x[i]和y[0]~y[i]的最长公共子序列实际上与x[0]~x[i-1]和 y[0]~y[i]的最长公共子序列一样或者与x[0]~x[i]和 y[0]~y[i-1]的最长公共子序列一样
即：f[i][j]=max(f[i - 1][j] ,f[i][j - 1])
第三步：确定程序实现方式
递推或记忆化搜索均可
f[i][j]=f[i-1][j-1]+1
f[i][j]=max(f[i - 1][j] ,f[i][j - 1])