美文网首页
动态规划(一)

动态规划(一)

作者: lqsss | 来源:发表于2018-03-25 12:57 被阅读0次

leetcode 198题目

给定一个数组(不同权重(钱)的店家),强盗可以抢不相邻的店家,求最大的钱数。

  1. 暴力搜索
  • 代码
public class HouseRobber {
    public int rob(int[] nums) {
        //return solve(nums.length-1 ,nums);
        return solve(0 ,nums);
    }

    private int solve(int idx, int[] nums) {
        if(idx > nums.length-1){
            return 0;
        }
        return Math.max(solve(idx+1,nums),solve(idx+2,nums) + nums[idx]);
    }
}

solve(int idx, int[] nums):抢下标为idx的店,最大的钱数。
return Math.max(solve(idx+1,nums),solve(idx+2,nums) + nums[idx]);
对于idx的店家只有两种可能:

  • 抢idx的话 solve(idx+2,nums) + nums[idx]
  • 不抢idx的话 solve(idx+1,nums)

结果:超时!
原因:

  • n->(n-2,n-3,n-4) 状态n由前n-2个状态决定 前n-2个状态每个都要算一遍

  • n-1->(n-3,n-4,n-5) 状态n-1由前n-3个状态决定 前n-3个状态每个都要算一遍

大量的重复运算,导致时间复杂度剧增,需要存储已经计算过的状态来解决这个问题

  1. 改进
    private static int[] res = null;

    public static int rob(int[] nums) {
        res = new int[nums.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = -1 ;
        }
        return solve(0, nums);
    }

    private static int solve(int idx, int[] nums) {
        if (idx > nums.length - 1) {
            return 0;
        }
        if (res[idx] >= 0 ) {
            return res[idx];
        }
        res[idx] = Math.max(solve(idx + 1, nums), solve(idx + 2, nums) + nums[idx]);
        return res[idx];
    }

用res数组来记录已经计算过的状态
if (res[idx] >= 0 ) { return res[idx]; }
计算过的话,直接返回,去除冗余计算。

动态规划

public class HouseRobber {

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length]; //记录抢到某个下标时的最优解
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[dp.length - 1];
    }
}
  1. 实质:递归
  2. 最优子结构
  • 子问题最优决策可以导出原问题的最优决策
  • 无后效性:抢了第n家店之后,后面的n-1家店不能抢(影响到了后面的决策);而这里进入了n-2,跳过了n-1,。
  1. 重叠子问题
    • 去冗余
    • 空间换时间

相关文章

网友评论

      本文标题:动态规划(一)

      本文链接:https://www.haomeiwen.com/subject/feyhcftx.html