20 Nov 2016

Recursion to 1 dimensional dynamic programing III

文章欢迎转载,但转载时请保留本段文字,并置于文章的顶部
Author: derek0883@gmail.com
本文原文地址:http://www.gorecursion.com/algorithm/2016/11/20/1d-dynamic3.html

This article will show you how to use recursion method solve problem, then easily lead to a 1 dimensional dynamic programing solution.

House Robber

Leetcode House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Video explanation

DFS O(2^n) time complexity

Start from index 0, Each time we have two options 1. Rob current house, the we can’t rob next, we should increase index by 2. 2. Don’t rob current house, then we should increase index by 1.

private int dfs(int[] nums, int pos) {
    if (pos >= nums.length)
        return 0;
    int opt1 = nums[pos] + dfs(nums, pos+2);        
    int opt2 = dfs(nums, pos+1);
    return Math.max(opt1, opt2);
}

BFS O(2^n) time complexity

class Node {
    int pos, total;
    Node(int i, int t) {pos = i; total = t;}
}
private int bfs(int[] nums) {
    Queue<Node> q = new LinkedList<>();
    int rob = 0;
    q.offer(new Node(0, 0));
    while (!q.isEmpty()) {
        Node n = q.poll();
        if (n.pos >= nums.length) {
            rob = Math.max(n.total, rob);
            continue;
        }
        q.offer(new Node(n.pos+2, n.total+nums[n.pos]));
        q.offer(new Node(n.pos+1, n.total));
    }
    return rob;
}

DFS + memorize O(n) time complexity

private int dfsCache(int[] nums) {
    int[] cache = new int[nums.length];
    Arrays.fill(cache, -1);
    return dfsCache(nums, 0, cache);
}

private int dfsCache(int[] nums, int pos, int[] cache) {
    if (pos >= nums.length)
        return 0;
    if (cache[pos] != -1) {
        System.out.println(pos+" ");
        return cache[pos];
    }
    int opt1 = nums[pos] + dfsCache(nums, pos+2, cache);
    int opt2 = dfsCache(nums, pos+1, cache);
    cache[pos] = Math.max(opt1, opt2);
    return cache[pos];
}

DP O(n) time complexity

private int dp(int[] nums) {
    if (nums.length == 0)
        return 0;
    if (nums.length == 1)
        return nums[0];
    if (nums.length == 1)
        return Math.max(nums[0], nums[1]);
    int[] fn = new int[nums.length];
    fn[0] = nums[0];
    fn[1] = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        int opt1 = nums[i] + fn[i-2];
        int opt2 = fn[i-1];
        fn[i] = Math.max(opt1, opt2);
    }
    return fn[nums.length-1];
}

DP O(1) space complexity

Again, every time we see it only using few previous item, we can reduce space complexity to O(1)

private int dpV2(int[] nums) {
    if (nums.length == 0)
        return 0;
    if (nums.length == 1)
        return nums[0];
    if (nums.length == 1)
        return Math.max(nums[0], nums[1]);
    int f0 = nums[0];
    int f1 = Math.max(nums[0], nums[1]);
    int f2 = f1;
    for (int i = 2; i < nums.length; i++) {
        int opt1 = nums[i] + f0;
        int opt2 = f1;
        f2 = Math.max(opt1, opt2);
        f0 = f1;
        f1 = f2;
    }
    return f2;
}