线性dp：大盗阿福（打家劫舍）
大盗阿福[*]本题与leetcode198题——打家劫舍的题意一模一样，阅读完本文以后可以尝试以下题目
力扣题目链接)
题目叙述：
阿福是一名经验丰富的大盗。趁着月黑风高，阿福计划今晚洗劫一条街上的店铺。这条街上一共有N家店铺，每家店中都有一些现金。阿福事先观察得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警员就会蜂拥而至。作为一向审慎作案的大盗阿福不愿意冒着被警员追捕的风险行窃。他想知道，在不惊动警员的情况下，他今晚最多可以得到多少现金?
输入格式
[*]输入的第一行是一个整数T，表示一共有T组数据。
[*]接下来的每组数据，第一行是一个整数N，表示一有N家店铺。
[*]第二行是N个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不凌驾1000。
输出格式
[*]对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警员的情况下可以得到的现金数量。
输入样例：
2
3
1 8 2
4
10 7 6 14输出样例：
8
24样例解释：
[*]对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。对于第二组样例，阿福选择第1和4家店铺行窃获得的现金数量为10+14=24.
动态规划思路分析
[*]设我们打劫的店铺数量为i，获取的价值和为dp ,那么dp明显是i的一个函数，那么我们就用dp作为状态变量，dp表示偷前i家店铺所能获取的价值最大值
状态变量以及它的含义
[*]由上面分析可知，我们设立dp 作为状态变量，并且dp的含义是偷前i家店铺所能获取收益的最大值.
递推公式
[*]我们设dp ，在i的这个位置有两种状态：
[*]1.第i家店铺不偷——dp=dp
[*]2.第i家店铺偷——dp=dp+w，w为第i家店铺的价值
详细细节如下图所示：
[*]https://img2024.cnblogs.com/blog/3476421/202408/3476421-20240820154741203-371328740.png
遍历顺序：
[*]由上面两步分析可知，dp的状态一定是由前面dp，dp，推出来的，所以说遍历顺序一定是从前向后遍历。
如何初始化？
[*]我们首先得处理好边界条件：dp和dp怎么处理？
[*]偷前0家店铺的最大价值显然是0，偷前1家店铺的最大价值显然为w
[*]处理好边界条件以后，我们再从前向后，依据递推公式进行递推就行了
举例验证dp数组
下标：1，2，3，4
w：10，7，6，14
dp：10，10，16，24
[*]通过样例2分析可知，我们的dp数组没有分析错。因此我们验证了我们的dp数组的正确性。
优化
[*]我们可以用dp的状态直接推出dp的状态。
[*]我们状态表示可以优化成：
[*]f表示不偷第i家店铺能获取的最大值
[*]f表示偷第i家店铺能获取的最大值
[*]那么我们的状态转移方程就可以从dp推出，不偷第i家店铺，那么我们就可以偷第i-1家店铺，也可以不偷，我们选取这两个之中的最大值，假如偷第i家店铺的话，第i-1家店铺我们一定只能选择不偷。
[*]不偷：dp=max(dp,dp)
[*]偷：dp=dp+w
https://img2024.cnblogs.com/blog/3476421/202408/3476421-20240820155855343-811906250.png
优化后的边界处理：
[*]不偷第1家店铺：f=0
[*]偷第1家店铺：f=w
优化后的代码处理：
scanf("%d",&t) while(t--){ scanf("%d",&n); for(int i=1;i
页:
[1]