113 Non bouncy Numbers

Problem 113

一个数如果左边的数字不会超过右边的数字，那么称为递增数，比如 134468

反之，如果右边的数字不会超过左边的数字，那么称为递减数，比如 66420

除了上述两种数之外的数称为跳跃数，比如 155349

随着 $n$ 的增加，跳跃数的比例在上升（非跳跃比例下降），比如一百万内有 12951 个非跳跃数，$10^{10}$ 以内有 277032 个非跳跃数。

求$10^{100}$以内有多少个非跳跃数。

很显然，不可能遍历，也就是说算法不能是指数增长，如果能和指数的大小成线性，那么就能很快给出答案。很直观的，要想办法从 $i$ 位数字中非跳跃数的个数构造出 $i+1$ 位数字中非跳跃数的个数。

我们首先考虑递增的情况。有一个 $i$ 位的递增数，如果起始数字是$d$，那么可以往它的前面插入一个小于等于 $d$ 的数字，构成 $i+1$ 位的递增数，反过来想，第一个数字是 $d$ 的 $i+1$ 位递增数的个数是 $d$ 到 $9$ 开头的 $i$ 位递增数的个数之和。那么，构造一个二维数组，一层一层往后计算即可。

private static long GetIncreasingCount()
{
    //          9,8,7...,3,2,1
    // 1 digits 1,1,1...,1,1,1
    // 2 digits 1,2,3...
    // n digits
    long[,] matrix = new long[Power, 9];
    for (int i = 0; i < 9; i++)
    {
        matrix[0, i] = 1;
    }
    for (int i = 1; i < Power; i++)
    {
        long count = 0;
        for (int j = 0; j < 9; j++)
        {
            count += matrix[i - 1, j];
            matrix[i, j] = count;
        }
    }
    return matrix.Cast<long>().Sum();
}

递减数的个数类似，需要特殊考虑下零即可。

最后，递增数和递减数有重合，比如 33，111，8888 这种，重复个数是 9 乘以幂次数，这里是 100。