数位DP题目的讨论
数位DP题目的讨论
说明：
就目前来说，所遇见的数位DP的题目类型主要可以分为以下几种类型：
1、各个位之间数字的差异统计
典型的题目有：Classy Numbers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
2、数字的符合要求统计
典型的题目有：[P2657 SCOI2009] windy 数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 长白崎の个人博客！
wechat
alipay
相关推荐
2023-05-22
数位DP模板
数位DP 说明： 数位DP是为了解决某些数字匹配上面的问题，其中经典的写法是套用DFS算法实现数位DP。 视屏教学： 数位DP E37 数位DP Windy数_哔哩哔哩_bilibili 这里说一下，前导零的意思，就是这个数字的前面都是零，比如说我们要dp的数字的最数字的位数为123。但是我们在进行dfs的DP的时候会从1开始，那么一开始我们从1开始dfs的时候那么就是001。也就是前面占位的都是零，也就叫做前导零。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182import java.util.Arrays;import java.util.Scanner;/** * @description: 数位DP * 这个是一个数位DP的模板，这里的数位DP主要是利用DFS来实现的。 * @author 长白崎 *...
2025-06-08
树形DP
2025-06-08
状态压缩DP
2023-05-19
树形DP的讨论
树形DP的讨论 讨论： 关于树形DP。树形DP比较适合解决一些有相互关系和依赖的的题型，比较典型的有没有上司的舞会、金明的预算方案、这一类题目。 首先我先说一下关于树形DP，顾名思义其含义就是在树这种数据结构上进行DP算法的运算。 树上背包DP 讨论： 树上背包DP这类是比较典型的树形DP题目。其中主要写题步骤为这几点： 首先找到我们需要DP的容量。也就是我们常说的背包容积大小，然后就是找到我们的需要DP的物品，常规的树上DP题主要关键数据就这两个。这里我就拿比较典型的一道题来说一下。 (以下题目为蓝桥官方的VIP题，我看比较典型就把它截下来了) 由图可知，我们的背包容量为V。商场一共有N件物品。第i件物品的体积为$$w_i$$，价值为$$v_i$$，其中依赖的主物件为$$s_i$$。 这里我们定义从第二行输入的数据作为下标为1的物品，以此类推。在构建树的时候我们就以0作为根节点，1意思为第一件物品，2为第二件物品依次类推。 从这我们就可以下手，我们从测试数据作为例子进行引入。以下为我依据...
评论
