1000ms

Difficulty: 6

所属公司 : oppo

时间 :2025年8月31日场

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库 oppo机考题库，可解锁完整内容。

购买oppo机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（oppo机考题库），可解锁完整内容。

购买题库开通会员

思路解析

首先我们注意到：

数字中不允许有 $0$ ，每一位只能是 $1$ 到 $9$ ，这是一个类似整数划分的组合方案问题。
问题等价于：求将整数 $s$ 划分为若干个（顺序重要）正整数，每个数在 $1$ 到 $9$ 之间的方案数。
如果用 $f[s]$ 表示数位和为 $s$ 的香香正整数个数，那么可得递推式：

题目内容

给定一个非负整数 $s$ ，定义一个 香香的正整数 为由数字 $(1-9)$ 组成正整数，其数位之和恰好等于 $s$ 。请计算所有香香的正整数的总数，并对 $(10^9+7)$ 取模。

输入描述