王家屯的王二狗

复旦大学复试

二叉树(3) 动态规划(6) 搜索&查找(1) 题解(6)

/ 注册

全部文章 / 复旦大学复试（共8篇）

1143. 最长公共子序列 -LeetCode

代码： public: int longestCommonSubsequence(string text1, string text2) { int m = text1.size(); int n = text2.size(); vector&...

动态规划最长公共子序列复旦大学机试

2022-03-19

0 244

518. 零钱兑换 II-LeetCode

关键字：完全背包、组合数问题 dp[0][0] 即价值0的物品放到容量为0的背包，应该也算一种方案本题考查组合问题：问题求解为组合数，即dp[i][j] = dp[i-1][j] + dp[i][j - nums[i]] 个方案 public: int change(int amou...

动态规划背包问题组合数问题完全背包问题

2022-03-19

0 267

（2021复旦机试）目标和+背包问题模板

目标和（LeetCode经典背包问题）背包分类的模板： 0/1背包：外循环nums,内循环target,target倒序且target>=nums[i]; 完全背包：外循环nums,内循环target,target正序且target>=nums[i]; 分组背包：这个比较特殊，需要...

动态规划背包问题 2021复旦机试

2022-03-19

0 315

（2020复旦机试）序列

关键字：动态规划最大递增子序列变形问题要找到关键的最优子问题：把问题规模是i=0,i=1考虑清楚，依次的计算出来即可 dp[i][j] 即第i个位置为j时能达到的最小距离值，也有点像背包问题，有点像最大公共子序列问题代码： ">#include<vector> #inc...

动态规划 2020复旦机试最大递增子序列变形

2022-03-18

0 251

（2019复旦机试）最大连续子序列

关键字：动态规划、最大连续子序列和题目描述：本题OJ链接给定一个数字序列A1,A2…An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大和。输入输出格式输入描述: 第一行输入一个整数n，表示数列大小第二行输入n个整数输出描述: 输出一个整数，...

动态规划 2019复旦机试

2022-03-18

0 280

（2016复旦机试）求最大连续公共字串长度

关键字：动态规划、最大公共子序列（连续情况）题目描述：给定两个字符串，求最大公共字串的长度，长度小于1000 1111hellow2233 2222hellow32 转移方程： dp[i][j]：即包含str1[i] 和 str2[j]的两个元素为末尾的时候，的最大连续子序列的长度...

动态规划 2016复旦机试复旦大学

2022-03-17

0 305

（2011复旦机试）最长公共子序列

题目类型：动态规划、最长公共子序列问题描述：输入3个子串，输出这3个子串的最大公共子串输入： abcd acb abc 输出： ab 思路分析：本体需要输出的不是最长公共子序列的长度或者和，本题要输出最长公共子序列本身，因此dp数组的设计需要注意转移方程： dp[i][j][k]：...

动态规划复旦大学 2011复旦机试最长公共子序列

2022-03-17

0 339

（2014复旦机试）字符串的编辑距离

问题分类：动态规划问题描述：把两个字符串变成相同的三个基本操作定义如下：修改一个字符（如把a变成b）增加一个字符(如abed 变成abedd) 删除一个字符（如jackbllog 变成jackblog）针对于jackbllog到jackblog只需要删除一个或增加一个l 就可以把两...

动态规划复旦大学最长公共子序列 2014复旦机试

2022-03-17

0 301