1977. 划分数字的方案数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

你写下了若干正整数，并将它们连接成了一个字符串 num 。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是非递减的且没有任何数字有前导 0 。

请你返回有多少种可能的正整数数组可以得到字符串 num 。由于答案可能很大，将结果对 109 + 7 取余后返回。

示例 1：

输入：num = "327"
输出：2
解释：以下为可能的方案：
3, 27
327

示例 2：

输入：num = "094"
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。

示例 3：

输入：num = "0"
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。

示例 4：

输入：num = "9999999999999"
输出：101

提示：

1 <= num.length <= 3500
num 只含有数字 '0' 到 '9' 。

# 思路

# 解法

class Solution {
    public int numberOfCombinations(String num) {
        char[] chars = num.toCharArray();
        if (chars[0] == '0') return 0;
        int mod = (int) 1e9 + 7, len = num.length();
        long[][] dp = new long[len][];
        for (int i = len - 1; i >= 0; i--) {
            dp[i] = new long[len - i];
            if (chars[i] == '0') continue;
            dp[i][len - i - 1] = 1;
            for (int j = len - i - 2; j >= 0; j--) {
                int l = i + j + 1;
                if (dp[l].length > j && compareTo(chars, i, j)) {
                    dp[i][j] = dp[l][j];
                } else {
                    dp[i][j] = j + 1 < dp[l].length ? dp[l][j+1] : 0;
                }
                dp[i][j] = (dp[i][j] + dp[i][j + 1]) % mod;
            }
        }
        return (int) dp[0][0];
    }

    private boolean compareTo(char[] chars, int i, int j) {
        for (int a = i, b = i + j + 1; a <= i + j; a++, b++) {
            if (chars[a] < chars[b]) return true;
            if (chars[a] > chars[b]) return false;
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 总结

分析出几种情况，然后分别对各个情况实现

#Java