题目大概: 阿福只能偷不相邻的两个商店的钱,共有n个商店,问阿福最多能偷多少钱。 思路: dp[n]表示前n个商店最多偷的钱数。a[n]表示每个商店的钱数。 1。。。当前商店如果被偷,
题目大概:
阿福只能偷不相邻的两个商店的钱,共有n个商店,问阿福最多能偷多少钱。
思路:
dp[n]表示前n个商店最多偷的钱数。a[n]表示每个商店的钱数。
1。。。当前商店如果被偷,则dp[n]=dp[n-2]+a[n].
2。。。不被偷,则dp[n]=dp[n-1]。
感想:
一个递推题。
代码:
#include <iostream>#include <algorithm>
#include <cstring>
using namespace std;
int a[100001],dp[100001];
int main()
{int t,n;
cin>>t;
memset(dp,0,sizeof(dp));
for(int i=0;i<t;i++)
{cin>>n;
for(int j=1;j<=n;j++)
{
cin>>a[j];
}
dp[1]=a[1];
dp[2]=max(a[1],a[2]);
for(int j=3;j<=n;j++)
{
dp[j]=max(dp[j-1],dp[j-2]+a[j]);
}
cout<<dp[n]<<endl;
}
return 0;
}