动态规划分析问题五步曲

不清楚动态规划分析问题是哪关键的五步的少年们可以移步到
链接: 动态规划算法基础
这篇文章非常详细的介绍了动态规划算法是如何分析和解决问题的

题目概述

链接: 打家劫舍

1. 状态表示（题目要求+自己的经验）
   本题状态：分析第i个位置，发现第i个位置可以选择偷和不偷
   显然，一个状态表示是不够的，得分类讨论
   teal[i] :表示第i个位置偷所获得的最大收益
   noteal[i] : 表示第i个位置不偷所获得的最大利益

2. 状态转移方程推导
   对i位置进行分类讨论，若i位置偷，则i-1位置不偷 。若i位置不偷，则i-1位置可以偷也可以不偷。
   轻松得出状态转移方程
   

3. 初始化（防止越界+结合状态表示初始化）
   根据状态转移方程，当i = 0时会发生越界
   根据状态表示 :
   初始化令teal[0] = nums[0] 即可

4. 填表顺序（分析要填i位置前一个依赖状态的位置）
   本题两个dp表显然都是从左到右填表

5. 返回值（由题目要求来）
   因此我们并不确定最终位置偷的时候最大，还是不偷的时候最大
   所以返回 max(teal[n-1] 和 noteal[n-1]);

代码编写

有了动态规划五步曲我们就可以写出非常优雅的代码了

int rob(vector<int>& nums) {
        int n = nums.size();
        if(!nums.size()) return 0;

        vector<int> teal(n);
        vector<int> noteal(n);
        teal[0] = nums[0];

        for(int i = 1 ; i < n ; i++)
        {
            teal[i] = noteal[i-1] + nums[i];
            noteal[i] = max(noteal[i-1],teal[i-1]);
        }
        return max(teal[n-1],noteal[n-1]);
    }

少年，今天你又进步了一点点哟，明天继续加油吧