动态规划如何应用于大盗阿福的寻宝问题？

本文共计479个文字，预计阅读时间需要2分钟。

题目概述：阿福只能偷相邻的两个商店的钱，共有n个商店，问阿福最多能偷多少钱。

思路：dp[n]表示前n个商店最多能偷的钱数。a[n]表示每个商店的钱数。

1. 当前的商店如果被偷，那么最多能偷的钱数就是前一个商店的钱数加上当前商店的钱数，即dp[n]=dp[n-1] + a[n]。

2. 如果当前商店没有被偷，那么最多能偷的钱数就是前一个商店没有被偷时的最多钱数，即dp[n]=dp[n-1]。

3. 初始化dp[1]=a[1]，dp[2]=max(a[1], a[2])。

4. 遍历所有商店，计算dp[n]。

5. 输出dp[n]，即为最多能偷的钱数。

题目大概：

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