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

本文共计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]。

感想：

一个递推题。