Number of ways问题

一般来讲这类问题dp比较多，因为很多时候只要返回数量的话，并不一定要琼剧所有情况，有很多利用supproblem重复还有对称性的trick可以用。

Android Unlock Patterns，利用对称性，只要计算三种情况就可以了。在做dfs之前，维护一个skip的二维数组，skip[i][j]表示了从i跳到j需要的前提条件是你已经visit过了skip[i][j]。

public class Solution {
    public int numberOfPatterns(int m, int n) {
        if (n == 0) {
            return 0;
        }

        int[][] skip = new int[10][10];
        skip[1][3] = skip[3][1] = 2;
        skip[7][9] = skip[9][7] = 8;
        skip[1][7] = skip[7][1] = 4;
        skip[3][9] = skip[9][3] = 6;
        skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = skip[2][8] = skip[8][2] = 5;

        int result = 0;
        boolean[] visited = new boolean[10];
        result += dfs(1, skip, visited, m, n, 0, 1) * 4;
        result += dfs(2, skip, visited, m, n, 0, 1) * 4;
        result += dfs(5, skip, visited, m, n, 0, 1);

        return result;
    }

    private int dfs(int num, int[][] skip, boolean[] visited, int m, int n, int sum, int count) {
        if (count >= m) {
            sum++;
        }
        count++;
        if (count > n) {
            return sum;
        }

        visited[num] = true;
        for (int i = 1; i <= 9; i++) {
            if (num == i || visited[i]) {
                continue;
            }
            int s = skip[num][i];
            if (s != 0 && !visited[s]) {
                continue;
            }

            sum = dfs(i, skip, visited, m, n, sum, count);
        }
        visited[num] = false;
        return sum;
    }
}

解法二：dfs有返回值的写法，注意在dfs function里的for loop里的那一步，是sum = dfs(parameter)， 而不是sum += dfs(parameter)。因为我们每次都在方法的头上去更新sum。

public class Solution {

    public int numberOfPatterns(int m, int n) {
        int[][] skip = new int[10][10];
        skip[1][3] = skip[3][1] = 2;
        skip[1][7] = skip[7][1] = 4;
        skip[3][9] = skip[9][3] = 6;
        skip[7][9] = skip[9][7] = 8;
        skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = skip[2][8] = skip[8][2] = skip[4][6] = skip[6][4] = 5;

        boolean[] visited = new boolean[10];
        int sum = 0;
        sum += dfs(skip, visited, m, n, 1, 1, 0) * 4;
        sum += dfs(skip, visited, m, n, 1, 2, 0) * 4;
        sum += dfs(skip, visited, m, n, 1, 5, 0);
        return sum;
    }

    private int dfs(int[][] skip, boolean[] visited, int m, int n, int count, int pos, int sum) {
        if (count >= m) {
            sum++;
        } 
        count++;
        if (count > n) {
            return sum;
        }

        visited[pos] = true;
        for (int i = 1; i <= 9; i++) {
            if (pos == i || visited[i]) {
                continue;
            }
            int skip_num = skip[pos][i];
            if (skip_num != 0 && !visited[skip_num]) {
                continue;
            }

            sum = dfs(skip, visited, m, n, count, i, sum);
        }
        visited[pos] = false;

        return sum;
    }
}

Decode Ways， 跟斐波那契数列，还有爬楼梯， 还有house robber都是同一类题，dp[i]是跟dp[i - 1]和dp[i - 2]有关的，看具体题目来分析之间的关系。这道题跟爬楼梯基本上是同一道题。

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int[] dp = new int[s.length() + 1];
        dp[0] = 1;

        for (int i = 1; i <= s.length(); i++) {
            char c = s.charAt(i - 1);
            if (c >= '1' && c <= '9') {
                dp[i] += dp[i - 1];
            }
            if (i >= 2 && s.charAt(i - 2) != '0') {
                int num = Integer.parseInt(s.substring(i - 2, i));
                if (num >= 10 && num <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }

        return dp[s.length()];
    }
}

Combination Sum IV