[线性dp]leetcode198：打家劫舍(medium)

题目：

---

题解：

思路：线性 dp

• 状态表示f[i]：表示从前 i 件物品中选获得的最大金额数。
• 状态计算：根据第 i 个物品选不选进行划分。选第 i 个物品，由于要求不能选相邻的物品，那么可以由前 i-2 件物品获得到的最大值 f[i-2] 推得，即 f[i-2] + a[i]；不选第 i 个物品，那么直接由前 i-1 件物品获得到得最大值 f[i-1] 推得，即 f[i-1]。

---

代码如下：

const int N = 110;
// f[i]表示从前i件物品中选能得到最大金额数
int f[N];
class Solution {
public:
    int rob(vector<int>& a) {
        if(a.size()<2)return a[0];
        memset(f,0,sizeof f);
        int n=a.size();
        f[0]=a[0],f[1]=max(a[0],a[1]);
        // 进行状态转移
        for(int i=2;i<n;++i){
            f[i]=max(f[i-2]+a[i],f[i-1]);
        }
        return f[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17