方法：动态规划1、创建一个数组dp，记录下数组arr不同位置为结尾时的最长上升子序列长度，可以得到如下的状态方程：如果存在arr[j] (j < i)小于该位置arr[i]，通过遍历前序的元素得到：dp[i] = max(dp[i], 1 + dp[j])；2、遍历完数组arr，数组dp中的最大值即为该数组的最长上升子序列长度。时间复杂度：o(n2)空间复杂度：o(n) class Solution { public: int LIS(vector<int>& arr) { // 特殊情况处理 if (arr.size() == 0) return 0; vector...

方法：动态规划根据题设，求存储组成aim的最少货币数，假设该问题有解，那么最后一个组成aim的货币一定是数组arr中的元素；因此我们可以将问题拆解，通过遍历数组arr，得到组成aim - arr[i]的最少货币数，那么组成aim的最少货币数即为1 + min(aim - arr[i])。1、使用一个大小为aim + 1的数组dp来存储0 - aim钱数所需的最少货币数，可以得到如下的状态方程： dp[i] = min(dp[i], 1 + dp[i - arr[j]]);2、如果问题有解，返回dp[aim]；否则返回-1。时间复杂度：o(n * aim)空间复杂度：o(aim) class S...

方法：动态规划1、遍历字符串，使用一个数组dp存储字符串不同位置结尾的译码结果次数，可以得到如下的状态转移方程如果当前字符可以和前面一个字符组成一个译码结果：dp[i] = dp[i - 1] + dp[i - 2]否则，dp[i] = dp[i - 1]2、数组最后一个元素就为字符串的译码结果次数。注意，当字符串中出现‘0’时，需要进行特殊处理时间复杂度：o(n)空间复杂度：o(n) class Solution { public: int solve(string nums) { // 特殊情况处理 if (nums[0] == '0') return 0; for (int i = 1;...

方法：动态规划1、遍历该矩阵的所有位置，使用一个二维数组dp记录不同位置为终点时的最小路径和，可以得到如下的状态方程：不处于第一行和第一列：dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i][j - 1])处于第一列不处于第一行：dp[i][j] = matrix[i][j] + dp[i - 1][j]处于第一行不处于第一列：dp[i][j] = matrix[i][j] + dp[i][j - 1]处于第一行且处于第一列：dp[i][j] = matrix[i][j]2、二维数组的右下角元素即为矩阵的最小路径和时间复杂度：o(nm)空间复杂度...

方法一：动态规划1、使用一个二维数组dp记录两个字符串不同位置结尾的公共子串长度，状态转移方程如下：字符相等时：dp[i][j] = 1 + dp[i - 1][j - 1]字符不相等时：dp[i][j] = 02、在遍历不同位置的同时，记录下最长的公共子串长度以及结尾的序号，可以得到最长的公共子串时间复杂度：o(n2)空间复杂度：o(n2) class Solution { public: string LCS(string str1, string str2) { vector<vector<int> > dp(str1.length() + 1, vector&l...

方法：动态规划主要分为以下两个步骤：1、获取到两个字符串s1、s2在不同位置结尾的最长公共子序列长度，用一个二维数组dp将长度存储起来；可以得到状态转移方程:如果字符相等：dp[i][j] = 1 + dp[i - 1][j - 1];如果字符不相等：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])2、从两个字符串的末尾向起点开始遍历，根据长度的大小来遍历，将得到的字符串进行反转即可得到最长的公共子序列。时间复杂度：o(n2)空间复杂度：o(n2) class Solution { public: string LCS(string s1, string s...

方法：动态规划根据题设：一旦你支付此费用，即可选择向上爬一个或者两个台阶。可以将问题分解为：最后选择爬一个台阶和两个台阶这两种方案的较小值即为最小花费。时间复杂度：o(n)。空间复杂度：o(n)。 class Solution { public: int minCostClimbingStairs(vector<int>& cost) { //需要爬上台阶，所以大小是数组大小加1 int n = cost.size() + 1; //记录爬到对应台阶最少的花费 vector<int> res(n, 0); for (int i = 2; i <= n; i...

方法一：递归斐波那契数列：f(n) = f(n-1) + f(n+1) （n>2）。可以将问题分解，使用递归解答。时间复杂度：o(2n)。空间复杂度：o(n)。递归栈深度 class Solution { public: int Fibonacci(int n) { if(n == 1 || n == 2) return 1; return Fibonacci(n - 1) + Fibonacci(n - 2); } }; 方法二：递归上述递归会有很多重复的计算，可以利用一个数组将数列保存下来，这样可以避免递归过程的重复计算。时间复杂度：o(n)。空间复杂度：o(n)。递归栈深度 cla...

方法：回溯+递归 按照题设可以得出：棋盘每一行有且只有一个皇后。根据该特性，使用数组res[n]记录每一行皇后所在的列数。从第一行开始，遍历每一列，判断不同列放置皇后是否有效（不能跟前面所放置的皇后 列数一样，不能处于对角线）；向下递归，当到达最后一行时，摆法加1，进行回溯。时间复杂度：o(n! * n)。遍历皇后的位置需要o(n!)，有效性判断需要o(n)。空间复杂度：o(n)。需要数组来记录每一行皇后所在的列数。  class Solution { public: int Nqueen(int n) { vector<int> res(n, 0); int num = 0; r...

方法：dfs（深度优先搜索）既然是查找最长的递增路径长度，那我们首先要找到这个路径的起点，起点不好直接找到，就从上到下从左到右遍历矩阵的每个元素。然后以每个元素都可以作为起点查找它能到达的最长递增路径。如何查找以某个点为起点的最长递增路径呢？我们可以考虑深度优先搜索，因为我们查找递增路径的时候，每次选中路径一个点，然后找到与该点相邻的递增位置，相当于进入这个相邻的点，继续查找递增路径，这就是递归的子问题。因此递归过程如下：终止条件： 进入路径最后一个点后，四个方向要么是矩阵边界，要么没有递增的位置，路径不能再增长，返回上一级。返回值： 每次返回的就是本级之后的子问题中查找到的路径长度加上本级的...

方法：递归 + 回溯首先我们可以把问题当成n个左括号和n个右括号的排列问题。那么要保证排列是正确的，只要保证排列时：1、第一个元素为左括号；2、排列时，使用右括号需要保证此时字符串中的左括号比右括号多。根据上面两个特性，可以使用递归来进行解答。具体做法：step 1：将空串与左右括号各自使用了0个送入递归。step 2：若是左右括号都使用了n个，此时就是一种结果。step 3：若是左括号数没有到达n个，可以考虑增加左括号，或者右括号数没有到达n个且左括号的使用次数多于右括号也可以增加右括号。时间复杂度：空间复杂度：o(n)。 class Solution { public: vector&lt...

方法：BFS（深度优先搜索）此题与有重复项数字的全排列相同，不再详细解答。时间复杂度：o(n*n!)空间复杂度：o(n) class Solution { public: vector<string> Permutation(string str) { //特殊情况处理（空字符串） if (str.size() == 0) return res; //按字典序排序 sort(str.begin(), str.end()); vector<bool> flag(str.size(), false); resort(flag, str, 0); return res; } ...

方法一：DFS（深度优先搜索） 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。使用深度优先搜索（dfs）：遍历矩阵，当遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向任意相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全部置为0，可以用递归实现。这样就将一个岛全部置0了。继续向下遍历矩阵重新进入上述的case。时间复杂度：o(nm)。n、...

方法：dfs+递归与无重复项的数字全排列几乎一样，只是在递归时需要一个条件来判断筛除重复的数字。时间复杂度：o(n*n!)空间复杂度：o(n) class Solution { public: vector<vector<int> > permuteUnique(vector<int>& num) { //将数组排序 sort(num.begin(), num.end()); vector<bool> flag(num.size(), false); dfs(num, flag, 0); return res; } private: ve...