1012. 至少有 1 位重复的数字【数位DP】

package main

import "fmt"

var debug = false

// 排列数
func A(i, j int) int {
    return f(i) / f(i-j)
}

func f(i int) int {
    if i == 1 || i == 0 {
        return 1
    }
    return i * f(i-1)
}

// 4567 => {7, 6, 5, 4}
func getNums(N int) []int {
    ret := make([]int, 0, 0)
    for N > 0 {
        ret = append(ret, N % 10)
        N /= 10
    }
    return ret
}

// 至少有一位重复数字的反面就是：所有数字都不一样
func numDupDigitsAtMostN(N int) int {
    nums := getNums(N)           // N的每个位上面的数字
    used := make([]int, 10, 10)  // 数字0~9的使用情况

    var total int                // 结果
    k := len(nums)               // N的位数

    if debug {
        fmt.Printf("nums[%v]\nused[%v]\ntotal[%v]\nk[%v]\n\n", nums, used, total, k)
    }

    // 情况1，高位为0
    // unms:    4    5    6    7
    //          0   1-9  0-9  0-9   9*A(9,2)
    //          0    0   1-9  0-9   9*A(9,1)
    //          0    0    0   1-9   9*A(9,0)
    // i:       3    2    1    0    循环三次，从k-1到1
    for i := k-1; i > 0; i-- {
        total += 9*A(9, i-1)

        if debug {
            fmt.Printf("情况1[i:%v]\n", i)
        }
    }

    // 情况2，高位不为0
    // unms:    4    5    6    7
    //         1-3  0-9  0-9  0-9   3*A(10-1,3)       循环i==3
    //          4   0-4  0-9  0-9   4*A(10-2,2)       循环i==2
    //          4    5   0-5  0-9   9*A(10-3,1)       循环i==1
    //          4    5    6   0-6   6*A(10, 0)        循环i==0
    //          4    5    6    7                      额外1次
    // i:       3    2    1    0    循环三次，从k-1到1
    for i := k-1; i>=0; i-- {
        num := nums[i]     // 当前数字
        // 最高位不为0，所以选第3位是从1开始，为1-3
        // 其余为可以从0开始，所有第2位是0-4，第1位是0-5，第0位是0-6
        j := 0
        if i == k-1 {
            j = 1
        }

        if debug {
            fmt.Printf("情况2[i:%v][j:%v][used:%v]\n", i, j, used)
        }

        // 处理第i位
        for ; j<num; j++ {
            if used[j] != 0 {
                continue            // 排除前面使用过
            }

            total += A(10 -(k-i), i)
        }
        // 处理完第i位
        used[num] ++               // 记录数字的使用状态

        // 情况4456，这个数肯定是不行的；执行完44后，就可以直接退出了！
        if used[num] > 1 {
            break
        }

        if i == 0 {
            total += 1    // 最后一种情况，不可以放在for外面，因为这个不是一定走得到的！
        }
    }

    return N - total   // 对立面
}

分析：
1、题目需要求数字N有多少个重复的数字，可以将其转换为求数字N有多少个不重复的数字，因为求不重复的数字可以更好地使用排列组合来求解；
2、N很大，如果遍历1~N，会超时
3、数位DP

情况1：高位为0##

    // 情况1，高位为0
    // unms:    4    5    6    7
    //          0   1-9  0-9  0-9   9*A(9,2)
    //          0    0   1-9  0-9   9*A(9,1)
    //          0    0    0   1-9   9*A(9,0)
    // i:       3    2    1    0    循环三次，从k-1到1

高位为0，则次高位可以选1-9，不可选0；
其余位是都可以选0-9，由于最高位选了1个，所以其余位有A(10-1,x)中选择，x为剩余位数；

情况2：高位不为0##

    // 情况2，高位不为0
    // unms:    4    5    6    7
    //         1-3  0-9  0-9  0-9   3*A(10-1,3)       循环i==3
    //          4   0-4  0-9  0-9   4*A(10-2,2)       循环i==2
    //          4    5   0-5  0-9   9*A(10-3,1)       循环i==1
    //          4    5    6   0-6   6*A(10, 0)        循环i==0
    //          4    5    6    7                      额外1次
    // i:       3    2    1    0    循环三次，从k-1到1

如果当前位是最高位，则选则需要从1开始，不能为0；
如果当前位不是最高位，则前面已经有非0的数字了，当前位可以从0开始；
以5所在的位为例，其实不能选择4，需要使用一个数组used记录数字的使用情况，DP？

if i == 0 {
    total += 1    // 最后一种情况，不可以放在for外面，因为这个不是一定走得到的！
 }

如44566，其实这种情况是走不到“边界值”的。