Increasing-Digits.md

题目地址（475. Increasing Digits）

https://binarysearch.com/problems/Increasing-Digits

题目描述

Given an integer n, return the number of positive integers of length n such that the digits are strictly increasing. Example 1 Input n = 2 Output 36 Explanation We have 12, 13, 14, ..., 89. Example 2 Input n = 1 Output 9 

前置知识

• 动态规划

思路

动态规划问题的关键就是：假设部分子问题已经解决了，并仅仅考虑局部，思考如何将已解决的子问题变成更大的子问题，这样就相当于向目标走进了一步。

我们可以定义状态 dp[i][j]， i 表示数字的位数，j 表示数字的结尾数字。

于是转移方程就是：dp[i][j] += dp[i - 1][k]，其中 k 是所有小于 j 的非负整数。最后只要返回 dp[n-1] 的和即可。

初始化的时候，由于题目限定了整数，因此需要初始化除了第一位的所有情况都为 1。

关键点

• 数位 DP

代码

代码支持：Python3

Python3 Code:

classSolution: defsolve(self, n): dp= [[0] *10for_inrange(n)] dp[0] = [0] + [1] *9foriinrange(1, n): forjinrange(1, 10): forkinrange(j): dp[i][j] +=dp[i-1][k] returnsum(dp[-1])

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。