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

目标和（LeetCode经典背包问题） 背包分类的模板： 0/1背包：外循环nums,内循环target,target倒序且target>=nums[i]; 完全背包：外循环nums,内循环target,target正序且target>=nums[i]; 分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板 问题分类的模板： 最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums); 存在问题(bool)...

关键字：动态规划最大递增子序列变形问题 要找到关键的最优子问题： 把问题规模是i=0,i=1考虑清楚，依次的计算出来即可 dp[i][j] 即第i个位置为j时能达到的最小距离值，也有点像背包问题，有点像最大公共子序列问题 代码： ">#include<vector> #include<algorithm> using namespace std; /* 6 1 4 2 8 5 7 */ int main() { int n; cin >> n; vector<int> numsA(n), numsB(n); for (int ...

关键字： 动态规划、最大连续子序列和 题目描述：本题OJ链接 给定一个数字序列A1,A2…An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大和。 输入输出格式 输入描述: 第一行输入一个整数n，表示数列大小 第二行输入n个整数 输出描述: 输出一个整数，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大 思路分析： 最大连续子序列和问题 dp[i] = max(dp[i-1]+nums[i], nums[i]) //dp[i]即为i位置能达到的最大的连续子序列和 代码： #include<iostream>...

关键字：动态规划、 最大公共子序列（连续情况） 题目描述： 给定两个字符串，求最大公共字串的长度，长度小于1000 1111hellow2233 2222hellow32 转移方程： dp[i][j]：即包含str1[i] 和 str2[j]的两个元素为末尾的时候，的最大连续子序列的长度 str1[i] == str2[j] 时，dp[i][j] = dp[i-1][j-1]+1; str1[i] != str2[j]时，dp[i][j] = 0; 代码： ">#include<vector> using namespace std; /* 1111hellow22...

题目类型：动态规划、最长公共子序列 问题描述：输入3个子串， 输出这3个子串的最大公共子串 输入： abcd acb abc 输出： ab 思路分析： 本体需要输出的不是最长公共子序列的长度或者和，本题要输出最长公共子序列本身，因此dp数组的设计需要注意 转移方程： dp[i][j][k]：为在三个字符串分别在i,j，k位置时，的最长的公共子序列字符串本身 dp[i][j][k] = dp[i-1][j-1][k-1] + str[i], 当str1[i] == str2[j] == str3[k] dp[i][j][k] = min(dp[i-1][j][k], dp[i...

问题分类：动态规划 问题描述： 把两个字符串变成相同的三个基本操作定义如下： 修改一个字符（如把a变成b） 增加一个字符(如abed 变成abedd) 删除一个字符（如jackbllog 变成jackblog） 针对于jackbllog到jackblog只需要删除一个或增加一个l 就可以把两个字符串变为相同。 把这种操作需要的最小次数定义为两个字符串的编辑距离L。 编写程序计算指定文件中字符串的距离。输入两个长度不超过512字节的ASCII字符串，在屏幕上输出字符串的编辑距离。 算法思路 思路与最长公共子串相似（但需要对dp数据进行一些优化）: dp[i][j]：即在字符串1的i位...

leetcode543. 二叉树的直径 ">#include<vector> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) :val(x), left(nullptr), right(nullptr){} }; TreeNode* insertBST(TreeNode* root, int x) { if (root == nullptr) { root = new TreeNode(x); return root...

习题10.1二叉搜索树（浙大） 生成两个二叉搜索树，然后按照遍历二叉树的方法判断两个序列生成的二叉树是否相同 ">#include<vector> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) :val(x), left(nullptr), right(nullptr){} }; //生成排序二叉树 TreeNode* insertBST(TreeNode* root, int x) { if (root == nullp...

例题10.4二叉排序树（华科） 关键：二叉排序树的插入、前序、中序、后序遍历 ">#include<vector> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} }; TreeNode* insert(TreeNode* root, int x) { if (root == NULL) { root = new TreeNode(x); } ...

例题10.3二叉排序树（华科） 关键字：二叉排序树的插入、二叉排序树输出父节点 #include<iostream> #include<vector> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} }; TreeNode* insertBST(TreeNode* root, int x, int father) { if (root =...

例题10.2二叉树遍历（华科） 关键字：二叉树构造、遍历二叉树 要点：通过给出的先序遍历序列和中序遍历序列要能构造出原本的二叉树来 #include <iostream> #include<vector> using namespace std; struct TreeNode { char data; TreeNode* left; TreeNode* right; TreeNode(char x) :data(x), left(nullptr), right(nullptr) {} }; TreeNode* buildTree(string strPr...

例题10.1二叉树遍历（清华） 通过字符串建立二叉树，然后中序遍历输出二叉树 关键字：构建二叉树、中序遍历二叉树 #include<vector> using namespace std; typedef struct TreeNode { char data; TreeNode* left; TreeNode* right; TreeNode(char x) :data(x), left(nullptr), right(nullptr){} }TreeNode; TreeNode* build(int &position, string s) { char ...

通过字符串建立二叉树，然后中序遍历输出二叉树 关键字：构建二叉树、中序遍历二叉树 #include<vector> using namespace std; typedef struct TreeNode { char data; TreeNode* left; TreeNode* right; TreeNode(char x) :data(x), left(nullptr), right(nullptr){} }TreeNode; TreeNode* build(int &position, string s) { char c = s[position++...