解法一
状态表示：
(f(i,0))：表示考虑前(i)家商店且不窃取第(i)家店铺的情况下所获得的最大价值。
(f(i,1))：表示考虑前(i)家商店且窃取第(i)家店铺的情况下所获得的最大价值。
状态转移：
[f(i,0)=max(f(i-1,0),f(i-1,1))
\
f(i,1)=f(i-1,0)+w[i]
]
const int N=1e5+10;
int w[N];
int f[N][2];
int n;
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
f[1][0]=0;
f[1][1]=w[1];
for(int i=2;i<=n;i++)
{
f[i][0]=max(f[i-1][0],f[i-1][1]);
f[i][1]=f[i-1][0]+w[i];
}
cout<<max(f[n][0],f[n][1])<<endl;
}
//system("pause");
return 0;
}
解法二
如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。
如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 (k ~ (k>2))间房屋，有两个选项：
- 偷窃第 (k) 间房屋，那么就不能偷窃第 (k−1) 间房屋，偷窃总金额为前 (k−2) 间房屋的最高总金额与第 (k) 间房屋的金额之和。
- 不偷窃第 (k) 间房屋，偷窃总金额为前 (k−1) 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 (k) 间房屋能偷窃到的最高总金额。
用 (dp[i]) 表示前 (i) 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
[dp[i]=max(dp[i-2]+w[i],dp[i-1])
]
边界条件为：
[egin{cases} extit{dp}[0] = extit{nums}[0] & 只有一间房屋，则偷窃该房屋 \ extit{dp}[1] = max( extit{nums}[0], extit{nums}[1]) & 只有两间房屋，选择其中金额较高的房屋进行偷窃 end{cases}
]
最终的答案即为( extit{dp}[n-1])，其中 (n) 是数组的长度。
const int N=1e5+10;
int w[N];
int f[N];
int n;
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
f[1]=w[1];
f[2]=max(w[1],w[2]);
for(int i=3;i<=n;i++)
f[i]=max(f[i-2]+w[i],f[i-1]); // 选或不选
cout<<f[n]<<endl;
}
//system("pause");
return 0;
}