题目解析
点的性质: 你正站在这个点上, 此时此刻的性质。
- 需要知道自己的上一个点(
last)的数字是多少。 - 自己前面是不是在边界上(不包含自己)？
- 自己的前面是不是全是零(前导零)？ 注意: 这个lead是不包含自己的。也就是说，如果
lead == 1，其实表自己前面都等于零的。 - 自己所在的层:
pos
数理逻辑方面的判断。
limit_{now} = limit_{last} && num_{pos} == nowNumber lead_{now} = lead_{last} && nowNumber == 0
我们可以根据上面的公式。, 得到: 从上一个点, 迁移到下一点的情况.
我真正的想要理解这个数位DP, 关键就在于多画图。 跟着图走一走。
状态转移方程:
显然，根据直觉都应该分为两种情况，一种是有限制的，一种是无限制的。
无限制的情况最简单: 如果自己所在的位置不在边界上,那么就是属于无限制情况: 因为自己的孩子(分支),可以随便分(0-9),那这个时候就可以使用记忆化,
FAQ
为什么在!lead的情况下才考虑缓存记忆化？ !limit我们能理解。
cpp
if( !limit && !lead && dp[pos][last] != -1)
{
return dp[pos][last];
}
其实很容易想到: 当lead== true, res记录的数值包含了0--9开头的所有的数字组合, 因为我们要把这些数拼接在另外一个数字的后面,那么这样就产生了错误。因为这样就不符合不要62的原则(0和1)
0
/ | | | | \
0 1 2 3 .. 9 lead = true
代码
cpp
#include <bits/stdc++.h>
using namespace std;
/**
* dp[i]
* Write me later
*/
int dp[15][20];
// dp 方程 dp[pos][last] 表示长度为pos+1 且 第pos+1高位数字为last的情况下,所有的可能
int num[15]; // 数字的拆分
// 在num 从高位到低位 在 dp上走
// pos 当前的位, 还代表层
// last 是上一个数字
int dfs(int pos,int last,bool limit, bool lead) {
// lead 全是0, 就返回0, 否则能到达这个位置 就是1
if( pos ==0 ) return lead ? 0 : 1;
if( !limit && !lead && dp[pos][last] != -1)
{
return dp[pos][last];
}
int up = limit ? num[pos] : 9; //上界
int res = 0;
for(int i = 0; i<= up;i++)
{
if( lead ) {
res += dfs(pos-1,i,limit && (i == num[pos]), lead && (i == 0) );
}
else {
if( abs(i - last) >=2)
res += dfs(pos-1,i,limit && (i == num[pos]), lead && (i==0));
// 这里 lead && (i==0) 一定是 false
}
}
if( !limit && !lead)
dp[pos][last] = res;
return res;
}
int solve(int x) {
if( x == 0) return 0;
int len = 0;
while(x) {
num[++len] = x % 10;
x /= 10;
}
return dfs(len,0,true,true);
}
int main (int argc, char *argv[]) {
memset(dp,-1,sizeof(dp));
int l ,r;
cin >> l >> r;
cout << solve(r) - solve(l-1) << endl;
return 0;
}
非递归(递推)写法解析
核心思路
预处理一张 DP 表 f[i][j]，表示 i 位数、最高位为 j 的 windy 数个数。递推关系：
边界：f[1][0..9] = 1（1 位数都是 windy 数）。
查询 [0, n] 的个数
拆解 n 为数字数组 str[1..cnt)，低位在前（如 123 → [3,2,1]）。
calc(n) 分三部分累加：
- 位数少于 n：所有
i位数（i < cnt-1），最高位1..9，累加f[i][j]。 - 位数相同、最高位更小：最高位取
1..str[cnt-1]-1，累加f[cnt-1][j]。 - 从高位到低位固定前缀：从次高位开始，当前位取
[0, str[i]-1]且与上一位差 ≥ 2 的，累加f[i][j]；若 n 自身某相邻位差 < 2，直接 break；否则最后加上 n 本身。
与记忆化递归的对比
| 方式 | 优点 | 缺点 |
|---|---|---|
| 递归 (1.cpp) | 思路直观，状态定义清晰 | 需要理解记忆化、limit/lead 控制 |
| 递推 (2.cpp) | 常数小，无递归开销 | 需要理解按位分段的计数逻辑 |
代码
cpp
/*-------------------------------------------------
* windy 数 - 非递归(递推)数位DP
* Author:Rainboy
* 2018-07-08 08:52
*-------------------------------------------------*/
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int a,b;
/* f[i][j]: i位数、最高位为j的windy数个数 */
/* 条件: 相邻两位数字差 >= 2 */
int f[12][10] = {0};
int str[100]; /* 拆解后的数字, 低位在前 */
int cnt; /* 数字位数 */
/* 将 n 拆成数字存到 str[1..cnt), str[1] 为个位 */
/* 例: n=123 -> str[1]=3, str[2]=2, str[3]=1, cnt=4 */
void div(int n){
cnt = 1;
if( n == 0) str[cnt] =0,cnt++;
while( n > 0){
str[cnt++] = n % 10;
n = n / 10;
}
}
/* 预处理 f 表 */
void init(){
int i,j,k;
/* 边界: 1位数, 最高位取 0-9 都只有 1 个 */
for(i=0;i<=9;i++) f[1][i] = 1;
/* 递推: 填 i 位数, 枚举第 i 位 j 和第 i-1 位 k */
for(i=2;i<=11;i++)
for(j=0;j<=9;j++)
for(k=0;k<=9;k++)
if( abs(j-k) >=2)
f[i][j] += f[i-1][k];
}
/* 计算 [0, n] 内 windy 数的个数 */
int calc(int n){
div(n);
int i,j,k,res = 0;
/* 1. 位数少于 n 的数 (位数 < cnt-1) */
/* 最高位不能为 0, 故 j 从 1 开始 */
for(i=1;i<cnt-1;i++)
for(j=1;j<=9;j++)
res += f[i][j];
/* 2. 位数与 n 相同, 但最高位 < str[cnt-1] */
for(i=1;i<str[cnt-1];i++)
res+= f[cnt-1][i];
/* 3. 从高位到低位固定前缀, 统计剩余位 */
for(i=cnt-2;i>=1;i--)
{
/* 当前位取 [0, str[i]-1], 且与上一位差 >= 2 */
for(j=0;j<str[i];j++)
if( abs(j-str[i+1]) >=2 )
res += f[i][j];
/* n 自己的这两位差 < 2, 后续不可能满足, 提前退出 */
if( abs(str[i] - str[i+1]) < 2)
break;
/* 所有位都满足条件, n 本身也是 windy 数 */
if( i== 1)
res+=1;
}
return res;
}
int main(){
init();
scanf("%d%d",&a,&b);
int ans;
ans = calc(b) - calc(a-1);
printf("%d\n",ans);
return 0;
}