robin呀

分类

二叉树(3) 动态规划(6) 复旦大学复试(8) 搜索&查找(1) 题解(6)

/ 注册

全部文章（共4篇）

例题12.7 点菜问题（北京大学复试）

例题12.7 点菜问题（北京大学复试）链接关键字：0-1背包、动态规划算法：设计dp[i][j] 用来存储将物品i放入背包中后可以达到的最大的价值j 分两种情况： CASE1: 当前背包没有足够空间，无法将商品 i 放入其中，此时的转移方程即为dp[i][j] = dp[i-1][j] CASE...

C++ 动态规划背包问题 0-1背包北京大学考研复试

2022-03-04

0 435

习题12.3合唱队形(北京大学复试题)

习题12.3合唱队形(北京大学复试题) 合唱队列是升级版的最大上升子序列问题 + 动态规划法考虑节点i，节点i左边需要的是最大上升子序列，节点右边是最大下降子序列问题，分别用dp1[i]和dp2[i]来存储 max(dp1[i] + dp2[i] -1) 即为最大的符合条件的队列的人数，用总人数...

C++ 动态规划北京大学最大上升子序列考研复试

2022-03-03

0 411

12.4拦截导弹（北京大学复试）

12.4拦截导弹（北京大学复试）问题分类：动态规划法 + 最长递增子序列问题 dp[i]取值的两种可能 nums[i]之前的元素都比i大，即最长的递归子序列只有nums[i]本身，那么dp[i] = 1 nums[i]之前存在numsj比nums[i]大，那么dp[i] = dp[j]+1; ...

C++ 动态规划北京大学最长递增子序列

2022-03-03

0 395

12.3最大子矩阵（北京大学复试题）

12.3最大子矩阵（北京大学复试题）王道课本P227 例12.3 本题是最大连续子序列的变种问题，需要将矩阵压缩成一维问题，当作最大连续子序列和问题来处理，再利用动态规划法问题求解dp[n] CASE 1: i == j (矩阵matrix的i行和j行为同一行时，就是最大连续子序列问题) CASE...

动态规划北京大学矩阵考研复试最大连续子序列

2022-03-02

0 655