Tag: DP - Light up the sky

十二月 01, 2021

数位DP数位DP问题关键：一般会问某一个区间里面满足某种性质的数的个数技巧一： $[x,y]$ = $f(y)-f(x-1)$ 类似前缀和的方式技巧二...

十一月 01, 2021

背包问题的一些拓展与处理装箱问题题目描述：有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。要求 n 个物品中，任取若干个装入箱内，...

九月 01, 2021

动态规划的本质不在于是递推或是递归，也不需要纠结是不是内存换时间。理解动态规划并不需要数学公式介入，只是完全解释清楚需要点篇幅…首先需要明白哪些问题不是...

九月 01, 2021

区间DP什么是区间 DP区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。令状...

九月 01, 2021

树形DP定义：在树上进行DP操作（没了）树的直径dfs两次dfs，第一次从任意一个点出发，跑到最远的一个点，然后第二次从最远的那个点开始跑，找到最远的一...

九月 01, 2021

背包问题：有n个物品，每个重量为vi,权值为wi，每个物品仅用一次,问在背包容量为W里能装的最大价值01背包核心特点：每件物品最多只能用一次集合条件：核心...

四边形不等式优化