首页 > Windows开发 > 详细

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

时间:2021-02-23 23:23:28      阅读:1      评论:0      收藏:0      [点我收藏+]

前言:

其实写这个博客的原因是在康其他人的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)

就是这样啦~~

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

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

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号