# Number of ways 类

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

## [Android Unlock Patterns](https://leetcode.com/problems/android-unlock-patterns/)

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

* 这个更多算是误会，实际上的连线没有那么复杂，走一个马步形状是不算 go through 的，因此最简单的办法，反正键盘数量有限，真正需要考虑的线路总共就 8 条，开个数组写出来就好了。
  * 如果 passThrough 是 0 ，说明 i，j 的连线不过其他点；
  * 其他情况说明 passThrough  的值就是路过需要检查的点。
* **这里的 dfs 结构更接近于 Tree 的形式，传进去的参数是当前在考虑的元素(但是已经确认是 valid input)，还没有做任何 visited 的标记和计数。因此有别于大多数其他 backtracking 的问题在循环里 backtrack，这个是在 dfs 函数自身的开始 / 结束处做 backtracking.**
* 另外一点是，我们有一个长度区间，而不仅仅是像大多数搜索问题那样，找到叶节点 / 找到解直接返回。这题当我们找到一个合理解的时候，需要继续往下探索，同时把以当前节点为起点，下面所有在合理深度范围的路径个数融合返回。
* 处理这个问题的一个简单，稍显暴力的做法，也是下面代码的做法，就是每次搜索时候固定深度，搜到目标深度就不搜了，返回 1 就行。优点是这样代码很好写；缺点是效率不高，因为同一个路径其实探了好几次。尤其在 “返回所有路径” 的搜索模式中，这种做法显然是不占优势的。

```java
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.

```java
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](https://leetcode.com/problems/combination-sum-iv/)

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

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

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

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

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

```java
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.

```java
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 而言的。

```java
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](https://leetcode.com/problems/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];**

```java
    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 论坛里关于这题还有好多种其他解法，比较简洁的有如下两个：

### 从左向右：

![](/files/-MUt7_yBMrr_PzxFMPeO)

```java
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];
    }
```

### 从右向左：

```java
    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];
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/search_and_backtracking_sou_suo_yu_hui_su/number_of_ways.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.