class Solution { public: int knapsack(int V, int n, vector<vector<int> >& vw) { vector<vector<int>> dp(n+1, vector<int>(V+1)); //dp[i][j] 表示::从i个物品选取,背包容量为j的最大重量; for(int i=1; i<=n; i++){ for(int j=1; j<=V;++j){ if( vw[i-1][0] <= j){ //第i物品的体积小于j体积,考虑是否放入,不...

class Solution { //组合,采用的是按照顺序进行选取,组合:有几个东西,多少组合在一起成一种情况,有多少种情况,选了这个或者不选这个直到选够了K个作为一种递归方式,另一种就是递归中有循环,一层递归就是选一位,循环尝试每一个数作为本位; public: vector<vector<int>> ans; vector<int> temp; vector<vector<int> > combine(int n, int k) { dp(n, k, 1); return ans; } void dp(int n, int re...

#include <vector> class Solution { public: set<string> ans; //采用集合的方式，自动去掉重复的元素； string temp = ""; vector<string> generatePermutation(string s) { if(s == "")return {""}; dp(s, 0); return vector<string>(ans.begin(), ans.end()); //将set转换成vector，注意构...

#include <type_traits> class Solution { //和全排列一样的思路 public: vector<string> ans; vector<string> Permutation(string str) { if(str.size() ==0)return {""}; dp(str, 0); return ans; } void dp(string& str, int index){ set<char> c; //因为str中有重复的字符，在进行交换时会把相同的字符多次放到本位，所以用...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <iostream> class Solution { public: int KthNode(TreeNode* proot, int k) { if(proot == nullptr){ return -1; } int count = 0; stack&...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: //因为是二叉搜索树，中序遍历既是递增的，按照顺序找到第K个就行； int ans = -1; int Num = 0; //Num用于记录当前检测是第几个数了，如果遇到了则更新ans int KthNode(TreeNode* proot...

class Solution { public: vector<vector<int>> direction = {{0, -1},{-1, 0},{0, +1},{+1, 0} }; //左上右下 vector<vector<int>> used; //防止一次检验字符串时，重复搜索 bool exist(vector<string>& board, string word) { used.resize(board.size(), vector<int>( board[0].size(), 0) ); //初始化...

class Solution { //题目限制很少，可以重复且排列不同也算，那么每一层递归时，数组全部需要检测， public: int ans = 0; int combination(vector<int>& nums, int target) { dp(nums, target, 0); return ans; } void dp(vector<int>& nums, int target, int curr){ if(curr > target)return; if(curr == target){ ++ans; return; } for...

#include <vector> class Solution { //全排列：给定一组不重复的元素，求出它们所有可能的排列方式（即所有顺序的组合），通过交换的方式确定一位的数字，因为交换过去的数字任然需要，如果是组合问题则尝试过的数字不再使用； public: vector<vector<int>> res; vector<vector<int> > permute(vector<int>& num) { sort(num.begin(), num.end()); dp(num, 0); sort(res.be...

class Solution { public: vector<vector<int>> ans; vector<int> temp; vector<int> used; vector<vector<int> > permuteUnique(vector<int>& num) { sort(num.begin(), num.end()); used = vector<int>(num.size(), 0); dp(num); return ans; } void dp(vector<i...

class Solution { //题目说得大矩阵是2*n的，小矩阵是2*1；然后多少种改变，可以发现其改变拆分成很多个的两个小矩阵的改变（倒一下），改变方式相同，只是位置不同，所以可以分改变的个数不同情况讨论，同时往下加个数，递归计算； public: int res=1; int rectCover(int number) { if(number == 0) return 0; dp(number, 1); return res; } void dp(int number, int start){ if(number-start+1<2){ return; } res += num...

class Solution { //题目说得大矩阵是2*n的，小矩阵是2*1；然后多少种改变，可以发现其改变拆分成很多个的两个小矩阵的改变（倒一下），改变方式相同，只是位置不同，所以可以分改变的个数不同情况讨论，同时往下加个数，递归计算； public: int res=1; int rectCover(int number) { if(number == 0) return 0; dp(number, 1); return res; } void dp(int number, int start){ if(number-start+1<2){ return; } res += num...

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return string字符串vector */ vector<string> ans; string temp; int left = 0; int right = 0; vector<string> generateParenthesis(int n) { left = right = n; dp(); return ans; } void dp(){ if(left == 0 &a...

class Solution { public: int maxSubArrayLengthTwo(vector<int>& nums) { // 遍历每一个元素,向前以及向后检验,得以当前为断点得最长; // 或者,记录前一个序列的后端，和长度，以及后一个序列的前段和长度，遇到断点就更新； // 改成使用数组记录,减去麻烦,用两个数组,一个记录以nums[i]结尾的最大子数组,一个记录以nums[i]开始的最大子数组; int n = nums.size(); if(n == 1)return 1; if(n == 2)return 2; vector<int&gt...