fyjjjj

动态规划

字符串(1) 平衡树(1) 树状数组(4) 背包(2) 递归(1)

/ 注册

全部文章 / 动态规划（共6篇）

躲藏

题目链接用dp[i,j]来表示前i个字符中匹配的字符j个数 j这个维度是子序列的长度这题中j的长度就为4 分别为1,2,3,4 则状态转移方程为： dp[i,1] = dp[i - 1][1] + (s[i] == 'c') dp[i,2] = dp[i - 1][2] + (s[i] ...

2020-11-08

0 536

拦截导弹

题目链接思路: 第一个问题很好解决，就是最长不上升子序列，利用贪心 + 二分的dp就可以解决，这里给一个二分查找的函数二分查找第二个问题是问给出的序列最少可以分成几个不上升子序列，其实这里有一个定理由Dilworth 定理，不上升子序列的最小划分数为 a 的最长上升子序列长度。所以第...

2020-11-03

0 525

大家一起来数二叉树吧

题目链接思路: 这个题一开始一点思路没有，感觉模拟的话是不太可能的，直接选择看题解，在看完题解后恍然大悟 1 dp状态 `dp[i,j] //n个结点，m个叶子结点有多少种形态 2 状态方程 dp[i,j] = dp[i,j] + dp[x][y] * dp[i - x - 1][j - y...

2020-11-02

0 564

牛牛与数组

题目链接题意：中文的，而且说的很明白，但是要注意，这个数组中的数可以重复思路： 1、dp状态 dp[i,j]表示了长度为i并以j结尾的数组符合条件的方案数有多少种 2、状态转移方程 dp[i,j] = sum(dp[i - 1][k] (k <= j) + dp[i - 1][x] ...

2020-11-01

0 741

删括号

题目链接题意：题目是中文的，不用我再进行赘述，但是这里要注意：删除的'('和')'必须是相邻的思路：说实话，要不是这个题被分到动态规划的题单里面，我是绝对不信这是一个dp题首先,我们先定义好dp变量,dp[i,j,k]表示1串前i在删除的'('数量-删去的')'为k时是否与2串的前j项相...

2020-11-01

1 695

被3整除的子序列

题目链接 1、dp变量 dp[len][m] 表示前len长度中，子序列各位和对3求余为m的子序列数量 2 递推公式, 1、当 (s[i] - '0') % 3 == 0时 dp[i][0] = dp[i - 1][0] + dp[i -1][0] + 1 dp[i][1] = dp[i - 1]...

2020-10-26

1 509