【DP】967. Numbers With Same Conse

问题描述：

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

Example 1:

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note:

1 <= N <= 9
0 <= K <= 9

解题思路：

让我们试着逐位写一些答案中的数字。
对于除第一位数字之外的每位数字，该数字最多有两个选项。以 9 位数字为例，这意味着最多只能有 9 * (2^8) 种可能。

算法：
一个 N 位数字可以看作只是在一个 N-1 位数字后添加了最后一位数字。如果该 N-1 位数字是以数字 d 结尾，则 N 位数字将以 d-K 或 d+K 结束（前提是这些数字在 [0，9] 之间）。除了从一位数字初始化，算法只需要迭代 N - 1 次就能得到最后的答案。

我们将这些数字存储在 Set 结构中，以避免重复。

注意：只有 1 位数字能以 0 开头（数字 0）。

举例：
比如 N = 3，K = 4，我们在上一次迭代中可以得到数字 51，那么接下来需要构造的是 515 （51(-3) 最后一位小于 0 越界了，不考虑）；在上一次迭代中可以得到数字 26，那么接下来需要构造的是 262 （26(10) 最后一位大于 9 越界了，不考虑）。

注意：当 N =1 时， 无论 K 为多少，答案都是 [0,1,2,3,4,5,6,7,8,9]，尽管题目中没有提示。这导致自己在编程的时候考虑太多了。

Python3 实现：

class Solution:
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        ret = {i for i in range(1, 10)}  # 初始化一个set
        for _ in range(N - 1):  # 迭代 N-1 次
            ret2 = set()
            for num in ret:
                d = num % 10  # 取最后一位
                if d - K >= 0:
                    ret2.add(10 * num + (d - K))
                if d + K <= 9:
                    ret2.add(10 * num + (d + K))
            ret = ret2
        if N == 1:  # 只有1位数字，还要包括0
            ret.add(0)
        return list(ret)  # set转化为list

print(Solution().numsSameConsecDiff(3, 7))  # [929, 707, 292, 181]
print(Solution().numsSameConsecDiff(2, 0))  # [33, 66, 99, 11, 44, 77, 22, 55, 88]
print(Solution().numsSameConsecDiff(1, 1))  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]