暑假（补）-4
DP（动态规划）
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。 动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
题的类型不同，但都是在基础上的动态规划的模板上进行改进。那么接下来就从几道简单的动态规划题型入手吧。
1.矩阵取数
一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。
例如：3 * 3的方格。
1 3 3
2 1 3
2 2 1
输入
第1行：N，N为矩阵的大小。(2 <= N <= 500)
第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N[i] <= 10000)输出
输出能够获得的最大价值。输入样例
3
1 3 3
2 1 3
2 2 1输出样例
11我们来用DP的思想来解决这个问题x 设矩阵是 . 假设我们已经知道了最大路径，并且经过（x, y）这个位置，为了从起点到终点得到的和最大，那 么从起点到 (x , y) 经过的数的和也一定要最大。这几乎是显然的。 这是理解这一题的重点。 走到 (x, y) 的上一步，可能是 （x-1, y） 或者（x, y-1）. 按照我门上面得出的结论，我们可以这样说： 如果从起点达到(x,y)的最优路径要经过(x – 1,y)或者(x,y – 1)则，从起点到达(x – 1,y)或者(x,y – 1)的 路径一定也必须是最优的。 所以只需要比较 到达(x – 1,y)或者(x,y – 1)的最优路径哪一个更加优。为了方便表示，我们用： 来表示起点到 （x，y）的最优路径长度。 所以,起点到 （x，y）的最优路径可以表示成：
f（x,y） = max( f(x-1,y) , f(x,y-1) )+ A [ x ] [ y ] 到了这里肯定会有疑问了，这怎么感觉和上面的贪心策略差不多？？ 其实不，这里是理解DP的重点。根据上面的这个递推公式，我门可以准确的推导出从起点到所有点 的最优解。是整体的最优。而贪心策略只是在局部做选择，是局部的最优。
AC
#include<iostream>
#include<algorithm>
using namespace std;
int a[600][600];
int main()
{
int n ;
cin>>n;
for(int i =0;i<n;i++)
for(int j =0;j<n;j++)
cin>>a[i][j];
for(int i =1;i<n;i++)
{
a[i][0]+=a[i-1][0];
a[0][i]+=a[0][i-1];
}
for(int i =1;i<n;i++)
for(int j =1;j<n;j++)
a[i][j]+=max(a[i-1][j],a[i][j-1]);
cout<<a[n-1][n-1]<<endl;
return 0;
}2.数字三角形
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5Sample Output
30DP
#include<iostream>
#include<algorithm>
using namespace std;
#include<stdio.h>
int n;
int a[200][200];
int DP(int i,int j)
{
if(i==n)
return a[i][j];
else
{
int x = DP(i+1,j);
int y = DP(i+1,j+1);
return max(x,y)+a[i][j];
}
}
int main()
{
while(cin>>n)
{
scanf("%d",&n);
for(int i =1;i<=n;i++)
for(int j =1;j<=i;j++)
scanf("%d",&a[i][j]);
printf("%d",DP(1,1));
}
return 0;
}非递归解决方案
#include<iostream>
#include<algorithm>
using namespace std;
int a[600][600];
int main()
{
int n ;
cin>>n;
for(int i =0;i<n;i++)
for(int j =0;j<n;j++)
cin>>a[i][j];
for(int i =1;i<n;i++)
{
a[i][0]+=a[i-1][0];
a[0][i]+=a[0][i-1];
}
for(int i =1;i<n;i++)
for(int j =1;j<n;j++)
a[i][j]+=max(a[i-1][j],a[i][j-1]);
cout<<a[n-1][n-1]<<endl;
return 0;
}这个DP思想是对的，并且答案也是对的，但当你submit时，TE了。因为有节点重复相加了，可以用记忆化搜索，解决重复相加问题。
记忆化搜索
#include<iostream>
#include<algorithm>
using namespace std;
int t;
int a[101][101],ans[101][101];
int dfs(int i ,int j)
{
if(i==t)
return a[i][j];
if(ans[i][j])
return ans[i][j];
int x =dfs(i+1,j);
int y = dfs(i+1,j+1);
return ans[i][j]= max(x,y)+a[i][j];
}
int main()
{
cin>>t;
for(int i=1;i<=t;i++)
for(int j =1;j<=i;j++)
cin>>a[i][j];
cout<<dfs(1,1);
return 0;
}3.最大序列和
Problem Description
Given a sequence a[1],a[2],a[3]……a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5Sample Output
Case 1:
14 1 4
Case 2:
7 1 6AC
#include<iostream>
#include<cstdio>
using namespace std;
int a[100100];
int main()
{
int t;
cin>>t;
int l =0;
while(t--)
{
int n ;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int p=1,start=1,end=1;
int maxsum=a[1];
for(int i=2;i<=n;i++)
{
if(a[i-1]+a[i]>=a[i])
{
a[i] = a[i]+a[i-1];
}
else
p =i;
if(a[i]>maxsum)
{
maxsum=a[i];
start=p;
end=i;
}
}
printf("Case %d:\n%d %d %d\n",++l,maxsum,start,end);
if(t)
cout<<"\n";
}
return 0;
}4.最长递增子序列
给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）
例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。
输入
第1行：1个数N，N为序列的长度(2 <= N <= 50000)
第2 - N + 1行：每行1个数，对应序列的元素(-10^9 <= S[i] <= 10^9)输出
输出最长递增子序列的长度。输入样例
8
5
1
6
8
2
4
5
10输出样例
5AC
#include<iostream>
#include<algorithm>
using namespace std;
int a[50001],dp[50001];
int main()
{
int n,ans=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(a[i]>a[j])
dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
return 0;
}提交后发现TE了，这是一个时间复杂度为O(n**2)的程序。
下面是一个时间复杂度为O(nlogn)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[50001];
int f[50001];
int main()
{
int n,maxn;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int len=1;
memset(f,0,sizeof(f));//创建一个新数组存放最长上升序列
f[0]=a[0];
for(int i=1;i<n;i++)
{
int pos=lower_bound(f,f+len,a[i])-f;//二分查找i+1个数中最长上升序列，a[i]的位置
f[pos]=a[i];
len=max(len,pos+1);//最长上升序列的数量
}
cout<<len<<endl;
return 0;
}