对于一个正整数x，如果x的每一位都不大于它右边一位上的数字，那么就称x是递增数，例如：112，4557，18899，111。
类似的，如果x的每一位都不小于它右边一位上的数字，那么就称x是递减数，例如：986，6331，77311，111。
递增数和递减数统称单调数。（111既是递增数，也是递减数，所以111肯定是单调数）
对于一个正整数x，如果x的每一位都不大于它右边一位上的数字，那么就称x是递增数，例如：112，4557，18899，111。
类似的，如果x的每一位都不小于它右边一位上的数字，那么就称x是递减数，例如：986，6331，77311，111。
递增数和递减数统称单调数。（111既是递增数，也是递减数，所以111肯定是单调数）
有多组输入。
每组输入一个数n。（n<=100)
对于每组输入数据中的n，输出小于10^n的单调数个数。
6
10
12951
277032
数位dp，想了好几种状态表示方案最后才成功，无语啊。。。
用dp[i][j]表示长度为i位，各位都不超过j时的单调数数量；
那么当i=1时，显然dp[i][j]=1 （j=1,2,...9)
当i=2时，以dp[2][3]为例，可能情况如下：
13，31， 23，32， 30， 33
共6种，下面分别讲解这六种情况：
13，31这两个数可以看作是分别在1这个数字前后添上3得到的，23，32同理；而03这种情况实际就是3，不符合，那么剩下30；而在3的前后添3都是33；
由以上可得规律：当i=2时，dp[2][j]=2+∑(dp[i-1][k]*2) (0<k<j)
而当i>2时，情况又有不同，以dp[3][3]为例：
通过之前的两步，已经可以得到得到i,j为(2,1),(2,2),(2,3)时的dp值，其具体情况如下：
| (i,j) | 可能情况 | dp[i][j] |
| (2,1) | 10,11 | 2 |
| (2,2) | 12,21, 20, 22 | 4 |
| (2,3) | 13,31, 23,32, 30, 33 | 6 |
| 可能情况 | ||
| 310,311 | ||
| 123,321, 320, 322 | ||
| 133,331, 233,332, 330, 333 |
但是！要注意，现在并没有找到所有情况，因为对于11，22这样的数，3仍可以随意加到其前后构成311，113，322，223，而33只能构成333.所以对于前j-1行，每行都要再多一种情况。
再检查一下是否所有可能情况已经找全了？
坑爹的我最后才发现竟然把300给忘了！
那么，当i>2时，最终得到的状态转移方程即为：dp[i][j]=∑(dp[i-1][k]+1) (1<=k<=j)
至此，规律已经找好了，接下来就是打表，计算
对于给定的n，要求的是小于10^n的单调数个数，即i可以等于1、2、3...n，j可以等于0、1、2...9；
那么，ans=∑∑dp[i][j] (i=1 to n)(j=0 to 9);
呼～解释完了，最后放一下AC代码：
（因为当时时间紧急，很多地方都写得很乱套，很多地方其实可以优化，不过总算是在比赛结束前两分钟的紧张时刻ac了，还是比较hp的，放上来仅作参考吧
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long dp[105][15];
int main()
{
long long n;
for(long long i=0;i<=9;++i)
{
dp[1][i]=1;
}
for(long long i=2;i<=2;++i)
{
dp[i][0]=0;
for(long long j=1;j<=9;++j)
{
for(long long k=1;k<j;++k)
{
dp[i][j]+=(dp[i-1][k]*2);
}
dp[i][j]+=2;
}
}
dp[1][0]=0;
for(long long i=3;i<=100;++i)
{
dp[i][0]=0;
for(long long j=1;j<=9;++j)
{
for(long long k=1;k<=j;++k)
{
dp[i][j]+=(dp[i-1][k]+1);
}
--dp[i][j];
dp[i][j]+=1;
}
}
while(cin>>n)
{
long long ans=0;
for(int i=1;i<=n;++i)
{
for(long long j=0;j<=9;++j)
{
ans+=dp[i][j];
}
}
cout<<ans<<endl;
}
return 0;
}原文：http://blog.csdn.net/harrypoirot/article/details/23611567