GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

PROBLEM SET

动态规划

按知识点筛选题目，系统巩固该考点。

共 605 题

重置

全部知识点基础数学知识模拟枚举深度优先搜索递推贪心基础排序栈区间动态规划最短路算法队列字符串结构体排序动态规划前缀和拓扑排序线性动态规划树形动态规划递归背包动态规划最近公共祖先二分答案并查集线段树 sort排序基础算法高精度分治素数筛法

题目列表

共 605 题

A66232 核电站一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数 1 < N < 50，2 ≤ M ≤ 5 )输出一个正整数S，表示方案总数。样例输入4 3样例输出13 2023年 递推动态规划计数问题状态转移 -- -- A66231 盒子与小球之二N个有差别的盒子（1<=N<=20）。你有A个红球和B个蓝球。0 <= A <= 15, 0 <= B <= 15。球除了颜色没有任何区别。你可以将球放进盒子。一个盒子可以同时放进两种球，也可以只放一种，也可以空着。球不必全部放入盒子中。编程计算有多少种放置球的方法。 2023年 递推动态规划排列组合组合计数 -- -- A63190 编程实现：路径最小和 创意编程组 动态规划二维数组路径最小和 -- -- A63189 编程实现：操作字符串 创意编程组 字符串动态规划编辑距离 -- -- A61503 字符串改造(trans.cpp)【问题描述】小明有一个字符串，由小写英文字母组成。小明准备对他的字符串进行改造，改造的方法是删除字符串中间的一部分字符。小明希望改造完后，新的字符串中的相邻字符都满足左边的字符小于等于右边的字符（a < b < … < z）。例如，对于字符串 happy，小明可以删除第一个字母，变成 appy，满足要求。或者小明删除第二字母，变成 hppy… 2020年 字符串动态规划最长不下降子序列 -- -- A63179 数学实验 创意编程组 贪心栈动态规划区间DP -- -- A63178 月球疏散行动 创意编程组 动态规划贪心算法排序 -- -- A61568 稳定串（stable）【问题描述】给定一个长度为n的01串，如果串中任意连续一段为1的子串长度都只为3，则称该串是稳定串，那么，对于长度为n的01串，要保证该01串为稳定串共有多少种方案？例如长度为7的01串中，0000000、1110000、0111000、1110111都是稳定串，而1011100、1111000、1111110则都不是稳定串。【 2021年 递推动态规划取模运算串计数 -- -- A61821 信息学奥赛练习题：数的划分【 2023年 递推动态规划整数划分 -- -- A61816 信息学奥赛练习题：平板涂色【 2023年 动态规划拓扑排序状态压缩图论建模 -- -- A61774 信息学奥赛练习题：楼间跳跃【 2023年 模拟贪心动态规划前缀和 -- -- A61772 信息学奥赛练习题：塔【 2023年 贪心动态规划前缀和区间合并 -- -- A68305 回家的路小Z家所在的街道都是横平竖直的，从空中俯视看，非常像一张方格表，由 n 行 m 列的方格组成，而小 Z 此刻正站在最左上角的格子中，想走回到最右下角的家中，他每次只能往右或者往下走一个格子，毕竟不能走回头路。由于小Z家附近在修路，就导致有些格子还不能走。好在小Z手上有一份地图，标注了哪些格子能走，哪些格子不能走。现在请你帮小 Z 算算他这次回家一共有多少种走法吧~【 2022年 递推动态规划二维数组路径计数 -- -- A61746 定义字符串的基本操作为:删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串A变成字符串乙的最少操作步数，称为字符串A到字符串B的编辑距离。字符串“ABCDEFG”到字符串“BADECG”的编辑距离为() 2023年 字符串动态规划编辑距离 -- -- A63141 编程实现：最大空白区 创意编程组 动态规划二维数组矩阵遍历最大矩形 -- -- A63431 因为希希在期末考试中的良好表现，爸爸将兑现帮她“清空购物车”的承诺。爸爸会带希希来到超市，允许她在指定区域任意挑选喜爱的商品，直到购物车装满为止，所有商品都由爸爸买单。希希十分珍惜这次难得的机会，提前一周来到超市，将自己喜欢的商品及其体积、价格列了一个清单（如下表所示），要回去好好研究一下。她之所以这么做，最根本的原因是购物车的容积有限，能容纳的物品体积之和不超过20。假设上述商品在超… 计算思维组 动态规划背包问题最优化 -- -- A63402 因为希希在期末考试中的良好表现，爸爸将兑现帮她“清空购物车”的承诺。爸爸会带希希来到超市，允许她在指定区域任意挑选喜爱的商品，直到购物车装满为止，所有商品都由爸爸买单。希希十分珍惜这次难得的机会，提前一周来到超市，将自己喜欢的商品及其体积、价格列了一个清单（如下表所示），要回去好好研究一下。她之所以这么做，最根本的原因是购物车的容积有限，能容纳的物品体积之和不超过20。假设上述商品在超市的库… 计算思维组 动态规划背包问题最优化 -- -- A66165 下⾯的程序中，⼆维数组h和v分别代表如下图所⽰的⽹格中的⽔平边的时间消耗和垂直边的时间消耗。程序使⽤动态规划计算从左下角到右上角的最⼩时间消耗，则横线处应该填写下列哪个选项的代码？（）。 2023年 动态规划二维数组网格路径 -- -- A66159 动态规划算法的时间复杂度⼀般为：必要状态的数量，乘以计算⼀次状态转移⽅程的时间复杂度。 2023年 动态规划时间复杂度状态转移 -- -- A66154 奖品分配班上有 N 名同学，学号从 0 到 N-1 。有 M 种奖品要分给这些同学，其中，第 i 种奖品总共有 ai 个（i=0,1,.....M-1 ）。巧合的是，奖品的数量不多不少，每位同学都可以恰好分到⼀个奖品，且最后剩余的奖品不超过1 个（即：）。现在，请你求出每个班级礼物分配的⽅案数，所谓⽅案，指的是为每位同学都分配⼀个种类的奖品。只要有⼀位同学… 2023年 动态规划组合数学排列组合取模运算 -- --