动态规划DP 状态机 模型分析 题目应用 大盗阿福 C++完整代码_状态转移方程f[i]=max(f[i−2]+w[i]

概览检索
动态规划DP 概览（点击链接跳转）

大盗阿福

原题链接

AcWiing 1049. 大盗阿福

题目描述

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺，每家店中都有一些现金。
阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

输入格式
输入的第一行是一个整数 T，表示一共有 T 组数据。
接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。
第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。

输出格式
对于每组数据，输出一行。
该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围
1≤T≤50,
1≤N≤105

输入样例：

231 8 2410 7 6 14

输出样例：

824

样例解释
对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。
对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。

题目分析

闫氏DP分析法

f[i]表示所有从前i家商店中选择的选法中获得现金数量最大的值。
对于第i家商店，我们可以选择/不选。
选择第i家商店，则一定要求不选择前一家i-1商店（保证不抢劫相邻的两家商店），则计算方程为f[i-2]+w[i]；
不选择第i家商店，则即从前i-1家商店中选择，则计算方程为f[i-1]。

得到状态转移方程为 $f[i]=max(f[i-2]+$