动态规划--大盗阿福

动态规划--大盗阿福

题目大概：

阿福只能偷不相邻的两个商店的钱，共有n个商店，问阿福最多能偷多少钱。

思路：

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

1。。。当前商店如果被偷，则dp[n]=dp[n-2]+a[n].

2。。。不被偷，则dp[n]=dp[n-1]。

感想：

一个递推题。

代码：

#include #include #include 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>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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。