Readme - Leetcode — ContextQMD

这是“双状态”DP最典型的一道题。它的特点是：每一轮的状态只取决于上一轮的状态；并且每一轮的状态只有两种，通常就是“取”或“不取”。

结合本题来说，是否打劫第k间房子（的收益），完全取决于是否打劫第k-1间房子（的收益）。令rob[k]表示打劫第k间的最大收益，norob[k]表示不打劫第k间的最大收益。我们可以分析出相邻两轮状态之间的递推关系：

cpp

rob[k] = norob[k-1];  // 想要打劫第k间房子，必须基于第k-1间房子没打劫。
norob[k] = max(rob[k-1],norob[k-1])+nums[k]; // 不打劫第k间房子的最大收益，显然对应了rob[k-1],norob[k-1]之间较大的值。

对于初始状态，我们可以直接考虑第0间房子是否打劫及其收益。这样状态转移方程可以从第1间房子开始适用。