Number of ways 类

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

Android Unlock Patterns

这题作为 google 近期热点题，挺有意思的，有趣在里面的细节和考点很多。

• 这个更多算是误会，实际上的连线没有那么复杂，走一个马步形状是不算 go through 的，因此最简单的办法，反正键盘数量有限，真正需要考虑的线路总共就 8 条，开个数组写出来就好了。

  • 如果 passThrough 是 0 ，说明 i，j 的连线不过其他点；

  • 其他情况说明 passThrough 的值就是路过需要检查的点。

• 这里的 dfs 结构更接近于 Tree 的形式，传进去的参数是当前在考虑的元素(但是已经确认是 valid input)，还没有做任何 visited 的标记和计数。因此有别于大多数其他 backtracking 的问题在循环里 backtrack，这个是在 dfs 函数自身的开始 / 结束处做 backtracking.

• 另外一点是，我们有一个长度区间，而不仅仅是像大多数搜索问题那样，找到叶节点 / 找到解直接返回。这题当我们找到一个合理解的时候，需要继续往下探索，同时把以当前节点为起点，下面所有在合理深度范围的路径个数融合返回。

• 处理这个问题的一个简单，稍显暴力的做法，也是下面代码的做法，就是每次搜索时候固定深度，搜到目标深度就不搜了，返回 1 就行。优点是这样代码很好写；缺点是效率不高，因为同一个路径其实探了好几次。尤其在 “返回所有路径” 的搜索模式中，这种做法显然是不占优势的。

public class Solution {
    public int numberOfPatterns(int m, int n) {
        int[][] passThrough = new int[10][10]; 
        boolean[] visited = new boolean[10];
        // Rows 
        passThrough[1][3] = passThrough[3][1] = 2;
        passThrough[4][6] = passThrough[6][4] = 5;
        passThrough[7][9] = passThrough[9][7] = 8;
        // Cols
        passThrough[1][7] = passThrough[7][1] = 4;
        passThrough[2][8] = passThrough[8][2] = 5;
        passThrough[3][9] = passThrough[9][3] = 6;
        // Diagnals
        passThrough[1][9] = passThrough[9][1] = 5;
        passThrough[3][7] = passThrough[7][3] = 5;

        int count = 0;

        for(int i = m; i <= n; i++){
            count += 4*dfs(visited, passThrough, 1, i - 1) + 
                     4*dfs(visited, passThrough, 2, i - 1) + 
                     dfs(visited, passThrough, 5, i - 1);
        }

        return count;
    }

    // take currently considering element 
    private int dfs(boolean[] visited, int[][] passThrough, int curNum, int lenRemain){
        if(lenRemain < 0) return 0;
        if(lenRemain == 0) return 1;

        int count = 0;
        visited[curNum] = true;
        for(int i = 1; i <= 9; i++){
            if(!visited[i] && (passThrough[curNum][i] == 0 || visited[passThrough[curNum][i]])){
                count += dfs(visited, passThrough, i, lenRemain - 1);
            }
        }
        visited[curNum] = false;

        return count;
    }
}

另一种沿途计数的代码实现是这样，具体细节处理我还是得学习一个。。这个写法就很适合输出所有路径了，改一下执行条件即可。

• 为什么初始传进去的 curLen = 1?

• 因为能作为参数传进去的 num ，都是valid move，当前的有效长度其实已经是 len + 1 了。

• 我们做的是一个 Tree 类 DFS，带着一个一定合理但又没加进去的元素进 DFS，长度 +1， 只在函数最开始和末尾做 backtracking.

public class Solution {
    public int numberOfPatterns(int m, int n) {
        int[][] passThrough = new int[10][10]; 
        boolean[] visited = new boolean[10];
        // Rows 
        passThrough[1][3] = passThrough[3][1] = 2;
        passThrough[4][6] = passThrough[6][4] = 5;
        passThrough[7][9] = passThrough[9][7] = 8;
        // Cols
        passThrough[1][7] = passThrough[7][1] = 4;
        passThrough[2][8] = passThrough[8][2] = 5;
        passThrough[3][9] = passThrough[9][3] = 6;
        // Diagnals
        passThrough[1][9] = passThrough[9][1] = 5;
        passThrough[3][7] = passThrough[7][3] = 5;

        return 4*dfs(visited, passThrough, 1, 1 , m, n) + 
               4*dfs(visited, passThrough, 2, 1, m, n) + 
               dfs(visited, passThrough, 5, 1,  m, n);
    }

    // 
    private int dfs(boolean[] visited, int[][] passThrough, int curNum, int curLen, int m, int n){
        int cumuCount = 0;
        if(curLen >= m) cumuCount++;
        if(curLen >= n) return cumuCount;

        visited[curNum] = true;
        curLen ++;
        for(int i = 1; i <= 9; i++){
            if(!visited[i] && (passThrough[curNum][i] == 0 || visited[passThrough[curNum][i]])){
                cumuCount += dfs(visited, passThrough, i, curLen, m, n);
            }
        }
        visited[curNum] = false;

        return cumuCount;
    }
}

Combination Sum IV

题目换成这样了之后依然是一个搜索问题，但是有了新的有趣特性。

主要在于这题和之前的 combination sum 还不太一样，它把 [1,3] 和 [3,1] 这种重复搜索算成两个解。于是强行制造了 overlap subproblems.

于是这题用搜索解会 TLE，加个 hashmap 做记忆化搜索，立刻就过了。

24ms ，时间复杂度较高，不如下面那个迭代的写法速度快。

O(n^d)，d代表得到 >= target 的搜索深度。

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        return dfs(nums, 0, target, new HashMap<Integer, Integer>());
    }

    private int dfs(int[] nums, int curSum, int target, HashMap<Integer, Integer> map){
        if(curSum > target) return 0;
        if(curSum == target) return 1;

        if(map.containsKey(curSum)) return map.get(curSum);

        int count = 0;
        for(int i = 0; i < nums.length; i++){
            count += dfs(nums, curSum + nums[i], target, map);
        }

        map.put(curSum, count);
        return count;
    }
}

考虑到可能的有效解路径一定是 [0,target] 之间，我们可以开一个定长的 array 做 hash，在 LC 上速度就快很多，1ms.

public class Solution {
    public int combinationSum4(int[] nums, int target) {
         int[] count = new int[target + 1];
         Arrays.fill(count, -1);
         return combinationSumHelper(nums, target, count);
    }

    private int combinationSumHelper(int[] candidates, int target, int[] count){
        if(target == 0) return 1;
        if(target < 0) return 0;
        if(count[target] != -1) return count[target];

        int sum = 0;
        for(int i = 0; i < candidates.length; i++){
            sum += combinationSumHelper(candidates, target - candidates[i],count);
        }

        count[target] = sum;
        return count[target];
     }
}

另外一种继承了背包类问题思想(Backpack III，单个元素无限取) 的 bottom-up 循环解法，非常的简洁：

时间复杂度 O(n * target)

注意这里内外循环的顺序不能错，要先按 sum 从小到大的顺序看，然后才是遍历每个元素。因为所谓 bottom-up，是相对于 sum 而言的，不是相对于已有元素的 index 而言的。

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[sum] = number of ways to get sum 
        int[] dp = new int[target + 1];

        // initialize, one way to get 0 sum with 0 coins
        dp[0] = 1;

        for(int j = 1; j <= target; j++){
            for(int i = 0; i < nums.length; i++){
                if(j - nums[i] >= 0) dp[j] += dp[j - nums[i]]; 
            }
        }

        return dp[target];
    }
}

Decode Ways

第一遍写的，改了好多次，如果是面试第一次遇到的话，遇到这类题切记 “细心”。

特殊 case : 11,101,110, 501..

• 如果遇到有歧义的情况，原理和 climbing stairs 类似，当前位置的合理解个数要考虑到前面两个子问题的合理解个数，即 dp[i] 要看 dp[i - 1] 和 dp[i - 2];

• 前一位不是 0 ，并且能和当前 digit 组成合理字母，就 dp[i] = dp[i - 1] + dp[i - 2];

• 前一位组不了，就不产生新路线，dp[i] = dp[i - 1];

• 重点在于 "0" 的处理。

  • 开头直接遇到 0，返回 0；

  • 任何位置连续遇到两个 0 ，无解，返回 0；

  • 前一位数不能和当前 0 组成字母，无解，返回 0；

  • 前一位数能和当前的 0 组成字母，dp[i] = dp[i - 2];

    public int numDecodings(String s) {
        if(s == null || s.length() == 0) return 0;
        if(s.charAt(0) == '0') return 0; // Can't start with 0

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

        for(int i = 1; i < s.length(); i++){
            int cur = s.charAt(i) - '0';
            int prev = s.charAt(i - 1) - '0';
            int num = prev * 10 + cur;

            if(cur == 0){
                if(prev == 0) return 0; // Error - 00
                else if(num <= 26) dp[i + 1] = dp[i - 1]; // we can't discard current 0
                else return 0; // 40, 50, etc.
            } else {
                if(prev != 0 && num <= 26) dp[i + 1] = dp[i] + dp[i - 1]; // "101" = 1 way
                else dp[i + 1] = dp[i];
            }
        }

        return dp[s.length()];
    }

LC 论坛里关于这题还有好多种其他解法，比较简洁的有如下两个：

从左向右：

public int numDecodings(String s) {
        if(s == null || s.length() == 0) return 0;
        if(s.charAt(0) == '0') return 0;

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

        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; i++) {
            int oneDigit = Integer.valueOf(s.substring(i-1, i));
            int twoDigits = Integer.valueOf(s.substring(i-2, i));
            if(oneDigit >= 1 && oneDigit <= 9) {
               dp[i] += dp[i - 1];  
            }
            if(twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }

从右向左：

    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) return 0;

        int[] memo = new int[n+1];
        memo[n]  = 1;
        memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;

        for (int i = n - 2; i >= 0; i--)
            if (s.charAt(i) == '0') continue;
            else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) 
                           ? memo[i+1]+memo[i+2] 
                           : memo[i+1];

        return memo[0];
    }