20 Nov 2016

Recursion to 1 dimensional dynamic programming I

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

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

Decode Ways

Leetcode Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

Video explanation

DFS O(2^n) time complexity

With the help of recursion tree, we can easily got a DFS or BFS solution with O(2^n) time complexity. Start from index=0, each step we have two options: 1. Decode 1 character, if it is ‘0’, we should terminate. 2. Decode 2 character, only if the value of those two <= 26.

Number of leaf node is the number of way to decode, each path from root node to leaf node is the decoded message. Each time we reach at leaf node, we return add 1.

private int dfs(String s, int pos) {
    if (pos < s.length() && s.charAt(pos) == '0')
        return 0;
    if (pos == s.length()) 
        return 1;
    int nWay = dfs(s, pos+1);
    int val = 0;
    if (pos+1 < s.length()) 
        val = Integer.parseInt(s.substring(pos, pos+2));
    if (val >= 10 && val <= 26)
        nWay += dfs(s, pos+2);
    return nWay;
}

BFS O(2^n) time complexity

Again BFS solution beautifully symmetric to DFS, On both termination condition and optional condition.

private int bfs(String s) {
    int nWays = 0;
    Queue<Integer> q = new LinkedList<>();
    q.offer(0);
    while (!q.isEmpty()) {
        int pos = q.poll();
        if (pos == s.length()) {
            nWays++;
            continue;
        }
        if (s.charAt(pos) == '0')
            continue;
        q.offer(pos+1);
        int val = 0;
        if (pos+1 < s.length()) 
            val = Integer.parseInt(s.substring(pos, pos+2));
        if (val >= 10 && val <= 26)
            q.offer(pos+2);
    }
    return nWays;
}

DFS + memorize O(n) time complexity

Recursion tree not only tells us how to implement DFS or BFS solution, but also give us clue how to optimize it. As you can see from the tree, each step we divide original problem to two smaller problem, marked in red circle. So if we already computed the number of way start from index pos, then next we don’t need compute again, we just reuse it.

private int dfsCache(String s) {
    int n = s.length();
    int[] cache = new int[n+1];
    for (int i = 0; i <= n; i++)
        cache[i] = -1;
    return dfsCache(s, 0, cache);
}
private int dfsCache(String s, int pos, int[] cache) {
    if (pos < s.length() && s.charAt(pos) == '0')
        return 0;
    if (pos == s.length()) 
        return 1;
    if (cache[pos] != -1)
        return cache[pos];
    int nWay = dfsCache(s, pos+1, cache);
    int val = 0;
    if (pos+1 < s.length()) 
        val = Integer.parseInt(s.substring(pos, pos+2));
    if (val >= 10 && val <= 26)
        nWay += dfsCache(s, pos+2, cache);
    cache[pos] = nWay;
    return nWay;
}

1 dimensional dynamic programming O(n) time complexity

Almost every Top down + memorize solution can be converted to a Bottom Up Dynamic Programming solution. Just do the following changes:

  1. Termination condition of Top Down DFS solution to initialization status of Bottom Up Dynamic Programming.
  2. Optional condition of Top Down DFS solution to the formula of Bottom Up Dynamic Programming.

So if s[0] is not ‘0’, we know there is one way to decode. Then we start from i=1.

if it is ‘0’, we terminate in DFS return 0, in DP, we initialized fn[i+1] as 0. Other wise, we have two options:

  1. we know the number of way is the same as fn[i],
  2. try to decode two character, s[i-1] and s[i], if the value is less than 27, then, we have fn[i+1] += fn[i-1];
private int dp(String s) {
    int n = s.length();
    int[] fn = new int[n+1];
    fn[0] = 1;
    fn[1] = s.charAt(0) != '0' ? 1 : 0;
    for (int i = 1; i < n; i++) {
        if (s.charAt(i) != '0')
            fn[i+1] = fn[i];
        int v = Integer.parseInt(s.substring(i-1, i+1));
        if (v >= 10 && v <= 26)
            fn[i+1] += fn[i-1];
    }
    return fn[n];
}

From the code we can see that each time, we only need access two previous element, So we can further reduce space complexity to O(1) A little tricky, please think about this question, when s[i] is ‘0’, why not set f2 to 0.

private int dpV2(String s) {
    int n = s.length();
    int f0 = 1;
    int f1 = s.charAt(0) != '0' ? 1 : 0;;
    int f2 = f1;
    if (n == 1)
        return f1;
    for (int i = 1; i < n; i++) {
        if (s.charAt(i) != '0')
            f2 = f1;
        else
            f2 = 0;
        int v = Integer.parseInt(s.substring(i-1, i+1));
        if (v >= 10 && v <= 26)
            f2 += f0;
        f0 = f1;
        f1 = f2;
    }
    return f2;
}