1164 dp

本题为3月21日23上半学期集训每日一题中A题的题解 题面 题目描述 卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D( $2\leq D\leq 100$)英尺。 卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了 ......

导读 ^ _ ^ 何为状态压缩？ 状态压缩的核心是对二进制的理解我们把一个状态表示成二进制从而用一个整数表示出各种状态在dp操作做，我们用位运算的角度去判断并且执行相应的操作 蒙德里安的梦想 思路 如果横着放确定，那么剩下的就是只能竖着放如何表示每行状态，我们将其用二进制去思考，即每个数都是二进制。 ......

树是一个由 $n$ 个节点 $n-1$ 条边所组成的无向无环连通图。 由于每个节点只有一个父亲，可以消除在具体求解中的后效性。 一般情况下，我们会采用dfs的方式一边遍历树一边 dp。 基础树形dp 例题 $1$：P1352 没有上司的舞会 和序列有关的 dp 设状态一般是设成：考虑前 $i$ 种物 ......

导读 ^ _ ^ 数位DP 数位DP，即是对数的每一位进行统计操作的DP问题。 计数问题 思路（分类讨论） 首先，如果一遍遍枚举，显示是不行的，因为1e8次这样，明显会超时。这类问题的关键是分类讨论，以及如何去从划分的角度思考问题。这样一思考，我们的复杂度降至 ：10 (统计数) * 2（划分数）* ......

题目链接 剑指 Offer 62. 圆圈中最后剩下的数字 思路 经典约瑟夫环问题，可以使用找规律的方法进行解决。 以 n = 8, m = 3为例，下面这幅图展示了模拟执行的全过程，用 F(n,m) 表示最后存活的人的索引。 从8个人开始，每次杀掉一个人，去掉被杀的人，然后把杀掉那个人之后的第一个人 ......

前言 ​ DP 与 DDP 均为GPU并行手段，目的是加快训练。 DP (Data parallelism) 如上图所示：DP其实只开了一个线程，并行算法实在多个设备上都拷贝了一份完整的模型参数，彼此之间可以独立计算。所以叫数据并行 前向传播时，GPU-1 会首先把所有的数据拿到，然后分发给其他的G ......

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的 ......

系列文章目录和关于我 一丶二叉树的遍历 1.二叉树遍历递归写法与递归序 了解过二叉树的朋友，最开始肯定是从二叉树的遍历开始的，二叉树遍历的递归写法想必大家都有所了解。 public static void process(TreeNode node) { if (node == null) { re ......

动态规划篇——线性DP 本次我们介绍动态规划篇的线性DP，我们会从下面几个角度来介绍： 数字三角形 最长上升子序列I 最长上升子序列II 最长公共子序列 最短编辑距离 数字三角形 我们首先介绍一下题目： /*题目概述*/ 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的 ......