数位dp入门-windy数

我真是太弱了!!!!!!

显然的数位dp,一开始我too young too simply的用dp[i][j]表示考虑到了第 i 位,且这一位的数是j的数量。但是,经过SMc的指点后,我发现这个沙雕的方程具有后效性,因为我们要保证每一位数与其相邻的数的绝对值之差大于等于2,我的做法就无法考虑下一位,然后就华丽爆零了。。。。。。。

数位dp的思想:

1、首先,答案一定与其大小无关,一般只考虑数的性质(例如每一位都满足某某性质)
2、转移注意后效性问题。
3、一般要考虑前导0,以及是否超限。

收获:

以后如果程序总是出锅,就想想算法是否有bug,建议用debug验证,并且注意大数据的测试。

原文地址:https://www.cnblogs.com/bullshit/p/9678073.html