【算法】数位DP
【题解】参考题解
记忆化搜索挺好写的，而且比DP+递推快。
大概思路是记录h(高度),pre(前一位数字),limit(限制)。
从根往叶子走，limit=0时，扫0~9判断符合条件就递归。
limit=1时，也就是当前位于n上，只能扫0~end-1，end就要limit=1来递归。
过程中记录一下f数组防止复算。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int f[20][20],l,r,a[20]; int dfs(int h,int pre,int limit) { if(h==-1)return 1; if(pre!=-1&&!limit&&f[h][pre]!=-1)return f[h][pre]; int end=limit?a[h]:9;int ans=0; for(int i=0;i<=end;i++) { if(pre==-1&&i==0)ans+=dfs(h-1,-1,end==0?1:0); else if(abs(i-pre)>=2||pre==-1) { if(i==end&&limit)ans+=dfs(h-1,i,1); else ans+=dfs(h-1,i,0); } } if(!limit)f[h][pre]=ans; return ans; } int solve(int x) { if(x==0)return 1; int n=0; while(x>0)a[n++]=x%10,x/=10; return dfs(n-1,-1,1); } int main() { scanf("%d%d",&l,&r); memset(f,-1,sizeof(f)); printf("%d",solve(r)-solve(l-1)); return 0; }
原文：http://www.cnblogs.com/onioncyc/p/6708455.html
