Number of Ways 类问题

这类问题一般用dp做的比较多，因为：

1. 不要求返回所有解，只需要个数。
2. 很多问题都有sub-problem重叠的特征。

351. Android Unlock Patterns

这道题的解法最鸡贼的地方就是先把two keys pass through another key的信息肉眼找出来然后存在一个2-d int array里。有了这个信息之后做起来就简单多了，基本就是无脑backtrack。

如果有些信息总量不大，很难通过计算得到，但却很容易通过肉眼观察得到，而且又对简化程序帮助很大，那就可以先肉眼观察然后hard-code一波。

class Solution {
    public int numberOfPatterns(int m, int n) {
        int[][] pass = new int[10][10];
        // intialize pass array
        pass[1][3] = pass[3][1] = 2;
        pass[1][7] = pass[7][1] = 4;
        pass[1][9] = pass[9][1] = 5;

        pass[2][8] = pass[8][2] = 5;

        pass[3][7] = pass[7][3] = 5;
        pass[3][9] = pass[9][3] = 6;

        pass[4][6] = pass[6][4] = 5;

        pass[7][9] = pass[9][7] = 8;

        boolean[] used = new boolean[10];
        return dfs(pass, used, 0, 0, m, n);
    }

    public int dfs(int[][] pass, boolean[] used, int i, int last, int m, int n){
        if (i == n)
            return 1;
        int sum = 0;
        if (i >= m)
            sum++;
        for (int j = 1; j <= 9; j++){
            if (used[j]) continue; // if the key has been used
            if (i > 0 && pass[last][j] > 0 && !used[pass[last][j]]) continue;  // pass some unused key
            used[j] = true;
            sum += dfs(pass, used, i+1, j, m, n);
            used[j] = false;
        }
        return sum;
    }

}

利用矩阵的对称性，我们可以对上面的方法进行优化：

| 1 | 2 | 3 | | 4 | 5 | 6 | | 7 | 8 | 9 |

1. 从四个角（1、3、7、9）开始搜索，得到的解的个数是一样的。
2. 从四个边的中点（2、4、6、8）开始搜索，得到的解的个数是一样的。

class Solution {
    public int numberOfPatterns(int m, int n) {
        int[][] pass = new int[10][10];
        // intialize pass array
        pass[1][3] = pass[3][1] = 2;
        pass[1][7] = pass[7][1] = 4;
        pass[1][9] = pass[9][1] = 5;

        pass[2][8] = pass[8][2] = 5;

        pass[3][7] = pass[7][3] = 5;
        pass[3][9] = pass[9][3] = 6;

        pass[4][6] = pass[6][4] = 5;

        pass[7][9] = pass[9][7] = 8;

        boolean[] used = new boolean[10];

        int res = 0;

        // search from the four corners
        used[1] = true;
        res += 4*dfs(pass, used, 1, 1, m, n);
        used[1] = false;

        // search from the mid point of four edges
        used[2] = true;
        res += 4*dfs(pass, used, 1, 2, m, n);
        used[2] = false;

        // search from the center
        used[5] = true;
        return res + dfs(pass, used, 1, 5, m, n);
    }

    public int dfs(int[][] pass, boolean[] used, int i, int last, int m, int n){
        if (i == n)
            return 1;
        int sum = 0;
        if (i >= m)
            sum++;
        for (int j = 1; j <= 9; j++){
            if (used[j]) continue; // if the key has been used
            if (i > 0 && pass[last][j] > 0 && !used[pass[last][j]]) continue;  // pass some unused key
            used[j] = true;
            sum += dfs(pass, used, i+1, j, m, n);
            used[j] = false;
        }
        return sum;
    }

}

91. Decode Ways

可以说是最经典的number of ways题了，没有之一。

思路很简单，记得也很牢了。

一个比较值得记住的地方是，可以优化到O(1) space：

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0)
            return 0;
        // int[] dp = new int[s.length()+1];
        // dp[s.length()] = 1;
        int dp2 = 1, dp1 = 0;
        if (s.charAt(s.length()-1) > '0')
            dp1 = 1;
        for (int i = s.length()-2; i >= 0; i--){
            int dp = 0;
            char ch = s.charAt(i);
            if (ch != '0'){
                dp += dp1;
                if (Integer.valueOf(s.substring(i, i+2)) <= 26)
                    dp += dp2;
            }
            dp2 = dp1;
            dp1 = dp;
        }
        return dp1;
    }
}