动态规划(DP)

GabrielxD

列車は必ず次の駅へ。では舞台は？私たちは？

累计撰写 675 篇文章
累计创建 128 个标签
累计收到 29 条评论

标签搜索

目录CONTENT

以下是动态规划(DP) 相关的文章

2022-11-29
【线性DP】编辑距离题目899. 编辑距离给定 nnn 个长度不超过 101010 的字符串以及 mmm 次询问，每次询问给出一个字符串和一个操作次数上限。对于每次询问，请你求出给定的 nnn 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。每个对字符串进行的单个字符的插入、删
- 2022-11-29
- 328
- 0
- 0
- 算法
2022-11-29
【线性DP】最短编辑距离题目902. 最短编辑距离给定两个字符串 AAA 和 BBB ，现在要将 AAA 经过若干操作变为 BBB ，可进行的操作有：删除–将字符串 AAA 中的某个字符删除。插入–在字符串 AAA 的某个位置插入某个字符。替换–将字符串 AAA 中的某个字符替换为另一个字符。现在请
- 2022-11-29
- 394
- 0
- 0
- 算法
2022-11-28
【动态规划, LCS】最长公共子序列题目897. 最长公共子序列给定两个长度分别为 NNN 和 MMM 的字符串 AAA 和 BBB ，求既是 AAA 的子序列又是 BBB 的子序列的字符串长度最长是多少。输入格式第一行包含两个整数 NNN 和 MMM 。第二行包含一个长度为 NNN 的字符串，表示字符
- 2022-11-28
- 688
- 0
- 0
- 算法
2022-11-25
【动态规划, LIS】最长上升子序列题目895. 最长上升子序列给定一个长度为 NNN 的数列，求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数 NNN 。第二行包含 NNN 个整数，表示完整序列。输出格式输出一个整数，表示最大长度。数据范围1≤N≤10001 \le N \le 10001≤N≤1000
- 2022-11-25
- 859
- 0
- 0
- 算法
2022-11-23
【动态规划】数字三角形题目898. 数字三角形给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 7 3 8 8 1 0 2 7 4 44 5 2
- 2022-11-23
- 452
- 0
- 0
- 算法
2022-11-23
【动态规划】分组背包问题题目9. 分组背包问题有 NNN 组物品和一个容量是 VVV 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vijv_{ij}vij ，价值是 wijw_{ij}wij ，其中 iii 是组号， jjj 是组内编号。求解将哪些物品装入背包，可使物品总
- 2022-11-23
- 1094
- 0
- 0
- 算法
2022-11-23
【动态规划】多重背包问题题目4. 多重背包问题 I5. 多重背包问题 II有 NNN 种物品和一个容量是 VVV 的背包。第 iii 种物品最多有 sis_isi 件，每件体积是 viv_ivi，价值是 wiw_iwi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。输入格式第一
- 2022-11-23
- 714
- 0
- 0
- 算法
2022-11-22
【动态规划】完全背包问题题目3. 完全背包问题有 NNN 种物品和一个容量是 VVV 的背包，每种物品都有无限件可用。第 iii 种物品的体积是 viv_ivi，价值是 wiw_iwi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，VN，VN，V，用
- 2022-11-22
- 557
- 0
- 0
- 算法
2022-11-22
【动态规划】01背包问题题目2. 01背包问题有 NNN 件物品和一个容量是 VVV 的背包。每件物品只能使用一次。第 iii 件物品的体积是 viv_ivi，价值是 wiw_iwi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数，N，VN，VN，V，用空
- 2022-11-22
- 588
- 0
- 0
- 算法
2022-11-20
【模拟, 动态规划】香槟塔题目799. 香槟塔我们把玻璃杯摆成金字塔的形状，其中第一层有 1 个玻璃杯，第二层有 2 个，依次类推到第 100 层，每个玻璃杯 (250ml) 将盛有香槟。从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了
- 2022-11-20
- 475
- 0
- 0
- 力扣
- 算法
2022-11-13
【动态规划】最小公倍数为 K 的子数组数目【力扣第 319 场周赛】题目6234. 最小公倍数为 K 的子数组数目给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中满足元素最小公倍数为 k 的子数组数目。子数组是数组中一个连续非空的元素序列。数组的最小公倍数是可被所有数组元素整除的最小正整数。示例 1 ：输入：nums =
- 2022-11-13
- 538
- 0
- 2
- 力扣
- 算法
2022-10-22
【动态规划】最小路径和题目64. 最小路径和给定一个包含非负整数的 m ×\times× n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。**说明：**每次只能向下或者向右移动一步。示例 1：输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径
- 2022-10-22
- 959
- 0
- 0
- 力扣
- 算法
2022-10-09
【动态规划】矩阵中和能被 K 整除的路径【力扣第 314 场周赛】题目6203. 矩阵中和能被 K 整除的路径给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往下或者往右，你想要到达终点 (m - 1, n - 1) 。请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对
- 2022-10-09
- 1040
- 0
- 0
- 力扣
- 算法
2022-10-07
【动态规划】最大升序子数组和题目1800. 最大升序子数组和给你一个正整数组成的数组 nums ，返回 nums 中一个升序子数组的最大可能元素和。子数组是数组中的一个连续数字序列。已知子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，若对所有 i（l <= i < r），n
- 2022-10-07
- 426
- 0
- 0
- 力扣
- 算法
2022-09-28
【优先队列, 动态规划, 多路归并】第 k 个数题目面试题 17.09. 第 k 个数有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。示例 1:输入: k = 5输出: 9解题方法一：优先队列哈希表思路本题与【优
- 2022-09-28
- 503
- 0
- 0
- 力扣
- 算法

1
2
3
4
5