题目

198. 打家劫舍

解法

\[fn= \left\{ \begin{array}{**lr**} max(f_{n-1}, f_{n-2}+nums[n]), & n\geq 2 \\ nums[0], & n=0 & \\ max(nums[1], nums[0]), & n=1 & \\ \end{array} \right. \]

class Solution {
    
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $ret = [
            $nums[0],
            max($nums[0], $nums[1]),
        ];

        for ($i = 2; $i < count($nums); $i++) {
            $ret[$i] = max($ret[$i - 1], $ret[$i - 2] + $nums[$i]);
        }
        
        return $ret[count($nums) - 1];
    }
}