打家劫舍

• 题目
• 函数原型
• 边界判断
• 算法设计：递归
• 算法设计：递归+记忆化搜索
• 算法设计：动态规划

题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

函数原型

C 的函数原型：

int rob(int* nums, int numsSize){}

边界判断

int rob(int* nums, int numsSize){
	if( nums == NULL || numsSize == 0 )
		return 0;
}

算法设计：递归

inline int max(int a, int b){
    return a > b ? a : b;
}

int __rob(int *nums, int numsSize, int index){
    if( index >= numsSize )
        return 0;
    
    int max_ans = 0;
    for(int i=index; i<numsSize; i++)
        max_ans = max( max_ans, nums[i] + __rob(nums, numsSize, i + 2) );

    return max_ans;
}

int rob(int* nums, int numsSize){
    if( nums == NULL || numsSize == 0 )
		return 0;

    return __rob(nums, numsSize, 0);
}

递归的复杂度：

• 时间复杂度： Θ ( 2 n ) \Theta(2^{n}) Θ(2n)
• 空间复杂度： Θ ( n ) \Theta(n) Θ(n)
   

算法设计：递归+记忆化搜索

int memo[1<<10];    // 左移10位，相当于乘10个2
inline int max(int a, int b){
    return a > b ? a : b;
}

int __rob(int *nums, int numsSize, int index){
    if( index >= numsSize )
        return 0;
    if( memo[index] )
        return memo[index];

    int max_ans = 0;
    for(int i=index; i<numsSize; i++)
        max_ans = max( max_ans, nums[i] + __rob(nums, numsSize, i + 2) );

    memo[index] = max_ans;
    return max_ans;
}

int rob(int* nums, int numsSize){
    if( nums == NULL || numsSize == 0 )
		return 0;

    return __rob(nums, numsSize, 0);
}

递归+记忆化搜索的复杂度：

• 时间复杂度： Θ ( n ) \Theta(n) Θ(n)
• 空间复杂度： Θ ( n ) \Theta(n) Θ(n)
   

算法设计：动态规划

从前往后递推…

状态转移方程： d p [ i ] = m a x ( d p [ i − 1 ] , d p [ i − 2 ] + n u m s [ i ] ) dp[i] = max(dp[i-1], dp[i-2] + nums[i]) dp[i]=max(dp[i−1],dp[i−2]+nums[i])

inline int max(int a, int b){
    return a > b ? a : b;
}

int rob(int* nums, int numsSize){
    int n = numsSize;
    if( n == 0 )
        return 0;
    if( n == 1)
        return nums[0];

    int memo[1<<10];
    memset(memo, 0, sizeof(int) * 1024);
    memo[0] = nums[0];
    memo[1] = max(nums[0], nums[1]);

	for(int i=2; i<n; i++)
		memo[i] = max(memo[i-1], (memo[i-2]+nums[i]));

    return memo[n-1];
}

or

从后往前递推：

inline int max(int a, int b){
    return a > b ? a : b;
}

int rob(int* nums, int numsSize){
    int n = numsSize;
    if( n == 0 )
        return 0;

    int memo[1<<10];
    memset(memo, 0, sizeof(int) * 1024);
    memo[n-1] = nums[n-1];

    for(int i=n-2; i>=0; i--)
        for(int j=i; j<n; j++)
            memo[i] = max( memo[i] , nums[j] + (j + 2 < n ? memo[j+2] : 0) );

    return memo[0];
}

动态规划的复杂度：

• 时间复杂度： Θ ( n ) \Theta(n) Θ(n)
• 空间复杂度： Θ ( n ) \Theta(n) Θ(n)