【动态规划9】小美的集合大小 - Problem Detail - CodeFun2000

ID: 2155

Difficulty: 6

本题为2024年4月13日美团实习开发岗机考原题

美团机考的介绍点击这里

题目思路

本题关键在于：相邻数位两两不同，那么也就意味着，对于任意一个数 $c$ ，我们需要更新集合的大小，一定是在集合中寻找不是以 $c$ 为结尾的那些子序列，然后往它们后面增加一个 $c$ ，放入集合中.

此时我们定义状态: $dp[i][j]$ 代表考虑了前 $i$ 个数位，并且结尾为数字 $j(0 \leq j \leq 9)$ 的子序列个数。

转移:

假设当前位置 $i$ 的数字为 $c$