动态规划
对这个问题,我们根据经验先用面值大的以求最大程度地解决问题,这就是贪心算法
重新分析刚才的问题,
所以,DP的核心思想:尽量缩小可能解空间
当然这道题还有一种在线处理算法,这里只讨论动态规划
//最大子序和
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int dp[1000];
int n,nums[100];
while(cin>>n)
{
//给数组赋值
for(int i=0;i<n;i++)
{
cin>>nums[i];
}
dp[0] = nums[0];
for(int i=1;i<n;i++) //从边界出发,确定每一个状态
{
dp[i]=max(nums[i],dp[i-1]+nums[i]);
}
//现在每一个状态的值都有了,找max
int k=0;
for(int i=0;i<n;i++)
{
if(dp[i]>dp[k])
{
k=i;
}
}
cout<<dp[k]<<endl;
}
return 0;
}
把以每个数结尾都设计成状态
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int f[100];
int dp[100]; //定义状态数组
int n;
cin>>n;
//赋值
for(int i=1;i<=n;i++)
{
cin>>f[i];
dp[i]=1; //此时每一个状态都只有自己一个
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(f[j]<f[i])
{
dp[i]=max(dp[i],dp[j]+1);
}
}
cout<<i<<dp[i]<<endl;
}
int m=0;
for(int i=1;i<=n;i++)
{
m=max(m,dp[i]);
}
cout<<m<<endl;
return 0;
}
DP会把每个状态都存起来,不必再做计算
计数类DP
又是这个经典的问题