Number of Ways

Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

nums = [1, 2, 3] target = 4

思路

看到这个number of possible combinations 就应该想到这一题应该是动态规划。

State: 和输入的数组无关，而是用target的值来作为一个维度，所以这是一个 背包问题。 f[i] 组成的target为i的时候可能有多少种解。

Function: f[i] = Sum{f[i - A[j]], j = 0 ~ n && i - A[j] > 0}

Init: f[0] = 1

Answer: f[target]

Code

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int[] dp = new int[target + 1];

        for(int i = 1; i <= target; i++) {
            for(int j = 0; j < nums.length; j++) {
                if(i - nums[j] > 0) {
                    dp[i] += dp[i - nums[j]];
                } else if (i == nums[j]){
                    dp[i] += 1; // 一个答案可能有多种可能
                } else {
                    break;
                }
            }
        }       
        return dp[target];
    }
}

思路2

主要在于这题和之前的 combination sum 还不太一样，它把 [1,3] 和 [3,1] 这种重复搜索算成两个解。于是强行制造了 overlap subproblems. 于是这题用搜索解会 TLE，加个 hashmap 做记忆化搜索，立刻就过了。

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

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

public int dfs(int[] nums, int curNum, int target, HashMap<Integer, Integer> map) {
    // boundary
    if(curNum > target) return 0;
    // base case
    if(curNum == target) return 1;
    // find in the cache first
    // curNum has the number of ways to add to the target
    if(map.containsKey(curNum)) return map.get(curNum);

    int count = 0;

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

    map.put(curNum, count);

    return count;
}

Decode Ways

Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

因为是求有多少种方法，并且这一位和前面的位数相关，所以是subproblem是有重叠的，当前的位置的合理解个数要考虑前面两个子问题的合理解数，可以用dp来做。

特殊的case: 101, 501, 110

• 遇到有歧义的情况，当前的位置的合理解个数要考虑前面两个子问题的合理解数，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组成字母，dp[i] = dp[i - 2]

public int numberOfDecode(String s) {
    if(s == null || s.length() == 0) {
        return 0;
    }
    // cann't start with 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 = 1; i < n; 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; // case--00
            if(num <= 26) dp[i + 1] = dp[i - 1];
            else return 0;
        } else {
            if(prev != 0 && num <= 26) dp[i + 1] = dp[i] + dp[i - 1]; // 可以和前面组成新的数
            else dp[i + 1] = dp[i];
        }
    }

    return dp[n];
}