动态规划--大盗阿福

题目大概：

阿福只能偷不相邻的两个商店的钱，共有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;
}