windy数的补充——数位dp中如何求[a,b]区间内的方案数

前言:

其实写这个博客的原因是在康其他人的windy数代码的时候,发现有的人的结果输出是work(b+1)-work(a),有的人的结果输出是work(b)-work(a-1),很奇怪为什么是这样的,所以就有了这篇博客

正文:

对于work(b+1)-work(a),其状态设置为dp[i][j]表示处理到第i位数,第i位数之前的值是j
对于work(b)-work(a-1),其状态设置为f[i][j]表示处理到第i位数,第i位数的值是j

很容易发现两个状态的差异,一个处理前面,一个处理后面,而正是因为这个差异,所以导致了结果的差异

对于第一个dp,我们发现如果枚举b-a这个区间,区间里的所有值都是可以被遍历的,所以我们直接按照常规方式输出work(b)-work(a-1)即可

对于第二个f,如果枚举b-a这个区间,最后枚举的只是绿色的两个格子(有界),所以输出结果是work(b+1)-work(a)

就是这样啦~~

原文地址:https://www.cnblogs.com/yxr001002/p/14438093.html