前面的文章介绍了动态规划可以解决重叠子和最优子结构问题，分别用了暴力破解、记忆化搜索、动态规划的方式解决。要知道函数意义的定义及其方法的实现是求解问题的重中之重，状态定义对应的就是函数的意义，状态转移对应的是函数的实现，不同的函数定义就有不同的函数实现。下面将用leetcode的House Robber来介绍动态规划的状态定义和状态转移。

一、题意及分析

1、题意

可以参考：

https://leetcode.com/problems/house-robber/description/

2、分析

把函数定义为考虑偷取[0...n-1]范围内的所有房子，于是问题就可以分解成如下的图：

可以看到上图是存在重复子问题和重复子结构的。

下面来看一下其中函数的定义，也就是状态的定义；还有就是函数的实现，也就是状态的转移所表达的意思。

可以看到求解0到n-1个范围内的问题，其实就是可以分解为求各个问题的最大值。

二、解法

无论是记忆化搜索还是动态规划的方法都要牢牢记住函数的定义及搜索记录的数组所表达的含义。例如：

函数定义

考虑抢劫nums[index...nums.size())这个范围的所有房子

其中的数组含义

// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
private int[] memo;

对函数的定义也就是对状态的定义，代表的是考虑偷取[x..n-1]范围内的房子。函数的实现和函数意义的定义是紧密相连的。相信千言万语都不如上代码来得更加直接明了。下面是具体的实现：

1、记忆化搜索

import java.util.Arrays;

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 记忆化搜索
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
import java.util.Arrays;

public class HouseRobber {

    // memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
    private int[] memo;

    /**
     * 考虑抢劫nums[index...nums.size())这个范围的所有房子
     * @param nums
     * @param index
     * @return
     */
    private int robHouse(int[] nums, int index){
        int size = nums.length;
        //
        if(index >= size ){
            return 0;
        }

        if(memo[index] == -1){
            int maxValue = 0;
            for (int i = index; i < size; i++) {
                maxValue = Math.max(maxValue, nums[i] + robHouse(nums, i + 2));
            }
            memo[index] = maxValue;
        }

        return memo[index];
    }

    /**
     * 考虑偷取[0,n-1]范围的所有房子
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return robHouse(nums, 0);
    }

    public static void main(String[] args) {
        int[] num1 = {1,2,3,1};
        int[] num2 = {2,7,9,3,1};
        HouseRobber houseRobber = new HouseRobber();
        System.out.println(houseRobber.rob(num1));
        System.out.println(houseRobber.rob(num2));
    }
}

输出的结果为：

2、动态规划方式

import java.util.Arrays;

public class HouseRobberDP {

    // memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
    private int[] memo;

    /**
     * 考虑抢劫nums[index...nums.size())这个范围的所有房子
     * @param nums
     * @return
     */
    private int robHouse(int[] nums){
        int size = nums.length;
        //
        memo[size-1] = nums[size-1];

        for (int i = size - 2; i >= 0; i--) {
            for (int j = i; j < size; j++) {
                memo[i] = Math.max(memo[i], nums[j] + (j+2 <= size -1 ? memo[j+2] : 0));
            }
        }

        return memo[0];
    }

    /**
     * 考虑偷取[0,n-1]范围的所有房子
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return robHouse(nums);
    }

    public static void main(String[] args) {
        int[] num1 = {1,2,3,1};
        int[] num2 = {2,7,9,3,1};
        HouseRobberDP houseRobber = new HouseRobberDP();
        System.out.println(houseRobber.rob(num1));
        System.out.println(houseRobber.rob(num2));
    }
}

输出的结果也是：

3、改变对状态的定义

如果改变对状态的定义将会有不同的实现。例如，下面对状态的定义

这个不同的状态的定义将有不同的实现。具体的实现如下：

（1）记忆化搜索

/// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 记忆化搜索, 改变状态定义
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
public class Solution3 {

    // memo[i] 表示考虑抢劫 nums[0...i] 所能获得的最大收益
    private int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return tryRob(nums, nums.length - 1);
    }

    // 考虑抢劫nums[0...index]这个范围的所有房子
    private int tryRob(int[] nums, int index){

        if(index < 0)
            return 0;

        if(memo[index] != -1)
            return memo[index];

        int res = 0;
        for(int i = 0 ; i <= index ; i ++)
            res = Math.max(res, nums[i] + tryRob(nums, i - 2));
        memo[index] = res;
        return res;
    }

    public static void main(String[] args) {

        int nums[] = {2, 1};
        System.out.println((new Solution3()).rob(nums));
    }
}

（2）动态规划

// 198. House Robber
/// https://leetcode.com/problems/house-robber/description/
/// 动态规划, 改变状态定义
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
public class Solution4 {

    public int rob(int[] nums) {

        int n = nums.length;
        if(n == 0)
            return 0;

        // memo[i] 表示考虑抢劫 nums[0...i] 所能获得的最大收益
        int[] memo = new int[nums.length];
        memo[0] = nums[0];
        for(int i = 1 ; i < n ; i ++)
            for (int j = i; j >= 0; j--)
                memo[i] = Math.max(memo[i],
                                   nums[j] + (j - 2 >= 0 ? memo[j - 2] : 0));

        return memo[n-1];
    }

    public static void main(String[] args) {

        int nums[] = {2, 1};
        System.out.println((new Solution4()).rob(nums));
    }
}

三、相似问题

1、

2、

3、