动态规划(Dynamic Programming)
动态规划问题一直是算法面试当中的重点和难点，并且动态规划这种通过空间换取时间的算法思想在实际的工作中也会被频繁用到。动态规划对思维是一个很大的挑战。
动态规划的基本思想就是把一个大问题分解成规模比它小的问题，然后再去解决大问题，仅此而已。比如我们要计算前n个数的和f(n)，那我们可以先计算出前n-1个数的和f(n-1)，然后再考虑f(n)和f(n-1)的关系:f(n) = f(n-1) + n，那么这个问题就可以从小问题开始一步一步解决，直至解决最终的问题。这个小问题的终点就是我们所说的初始状态，然后考虑f(n)和f(n-1)的关系，类似于数学归纳法的样子。
所以，动态规划一般分为4个步骤：
问题拆解
状态定义
方程定义
实现
还是放到以后写吧。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
下面介绍几种常见的，简单动态规划。
在所有动态规划中，最简单的应该就是线性动规了。
爬楼梯 HDU 2041
假设你正在爬楼梯，从第0层开始，到第n层，每次你可以爬1阶或者2阶，问从第0到第n阶楼梯共有多少种不同的爬法。
可以很简单想到：f(1)=1,f(2)=1,f(n)=f(n)+f(n-1).
最后那个式子就是状态转移方程了。
cin >> n;
f[1] = f[2] = 1;
for (int i=3;i<=n;i++) f[n] = f[n-1] + f[n-2];这其实和Fibonacci数列差不多，当n非常巨大时，朴素的作法行不通，就要用到矩阵快速幂了。
这题有几个变种
每次输入n，k，即每次最多可爬k阶楼梯，问爬到第n阶有多少种不同的方法。 实在记不起来在哪做的了。。先把f[1~k]初始化为1，然后再用朴素作法。
三角形最小路径之和 POJ 1163
输入一个三角形
[
·····[2],
····[3,4],
···[6,5,7],
··[4,1,8,3]
]
找出自顶向下的路径最短的一条。
dp[i][j] = min(dp[i+1][j],dp[i+1][j+1])+a[i][j];
#include <cstdio>
#include <algorithm>
using namespace std;
int a[105][105],b[105][105];
int main(){
int t,n;
scanf ("%d",&n);
for (int i=1;i<=n;i++) for (int j=1;j<=i;j++) scanf ("%d",&a[i][j]);
for (int i=n;i>=1;i--) for (int j=1;j<=i;j++)
b[i][j] = max(b[i+1][j],b[i+1][j+1])+a[i][j];
printf ("%d\n",b[1][1]);
return 0;
}最大子序和 洛谷P1115
这个就比较经典了！
输入一列数，求这个数列的连续非空的一段，是的其子段和最大。
这个题可以用线性动态规划解，也可以用分治法求解，都很巧妙。
此题如果不应用一些算法的话，乍一看是很茫然的，总不能把所有子段都试一遍？？那肯定不科学，2^n种情况。
先来看分治法求解。在这个长为n的序列中，我们把它分成左右均等的两部分，和最大的那个子段，要么完全在左半部分，要么完全在右半部分，要么两边都有，那么这样就可以分解规模了。
f[1-n] = max{f[1-mid],f[mid+1-n],tmp};
其中f[1-n]表示下标为1-n内的最优解，tmp表示从序列中心开始，分别向左右两端扩展得到的最大和的和。tmp代表的是左右两边都有的情况下的最优解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 200005
ll a[maxn];
ll search(int l,int r);
int main(){
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
cout << search(1,n);
return 0;
}
ll search(int l,int r){
if (l==r) return a[l];
if (r==l+1) return (ll)max(max(a[l],a[r]),a[l]+a[r]);
ll mid = (ll)max(search(l,(l+r)/2),search((l+r)/2+1,r)),now1,now2=0,ans1=-9999999,ans2=-99999999;
int temp = (l+r)/2;
ans1=now1=a[temp];
for (int i=temp-1;i>=l;i--){
now1 += a[i];
ans1 = max(ans1,now1);
}
for (int i=temp+1;i<=r;i++){
now2 += a[i];
ans2 = max(ans2,now2);
}
return (ll)max((ll)ans1+ans2,mid);
}动态规划求解。先假设在前i个序列中，最优解的最后一个数，要么是第i个数，要么不是，即前i个数的最优解要么包含第i个数，要么不包含。设出两个变量dp[i]，tmp，dp[i]表示前i个数得最优解，tmp表示在前个数中，以a[i]结尾的最大子段和。
状态转移方程：dp[i+1] = max(dp[i],max(a[i+1],tmp+a[i+1]))
tmp也要更新：tmp = max(a[i+1],a[i+1]+tmp);
#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
int a[maxn];
void read(int &x){ //这里x是整数，int,ll都可
int f=1;x=0;char s = getchar(); //f表示符号
while(s<'0' || s>'9'){if (s=='-')f = -1;s = getchar();}
while(s>='0' && s<='9'){x = x*10+s-'0';s=getchar();}
x *= f;
}
int main(){
int n;
read(n);
for (int i=1;i<=n;i++) read(a[i]);
int tmp,ans;
tmp = ans = a[1];
for (int i=2;i<=n;i++){
tmp = max(a[i],tmp+a[i]);
ans = max(ans,tmp);
}
printf ("%d",ans);
return 0;
}升级版：POJ2479
A为一个序列，求d[A].
正反求两遍dp，dp1[i]表示前i个数的最优解，dp2[i]表示i-n的最优解。然后在O(n)跑一遍原数组，去最大值即可。
d(A) = max(dp1[i]+dp2[i+1]);
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define wa -100000000
const int maxn = 5e4+5;
int a[maxn];
int dp1[maxn],dp2[maxn];
int main(){
int t,n;
scanf ("%d",&t);
while (t--){
scanf ("%d",&n);
memset(dp1,0,sizeof dp1);
memset(dp2,0,sizeof dp2);
for (int i=1;i<=n;i++) scanf ("%d",&a[i]);
int tmp = a[1]; dp1[1] = a[1];
for (int i=2;i<=n;i++){
tmp = max(a[i],a[i]+tmp);
dp1[i] = max(dp1[i-1],tmp);
}
tmp = a[n],dp2[n] = a[n];
for (int i=n-1;i>=1;i--){
tmp = max(a[i],a[i]+tmp);
dp2[i] = max(dp2[i+1],tmp);
}
int ans = wa;
//int ans = dp1[1]+dp2[2];
for (int i=1;i<n;i++)
ans = max(ans,dp1[i]+dp2[i+1]);
printf ("%d\n",ans);
}
return 0;
}
0 条评论