class Solution { public: int minMoney(vector<int>& arr, int aim) { if (!aim) return 0; if (arr.empty()) return -1; int lenarr = arr.size(); vector<int> dp(aim, 1e9); for (int j = 0; j < lenarr; j++) { for (int i = arr[j] - 1; i < aim; i++) { //外循环遍历arr，内循环遍历[arr[j]-1,aim]可以跳过一些...

#include <algorithm> #include <vector> class Solution { public: int minMoney(vector<int>& arr, int aim) { if (!aim) return 0; if (arr.empty()) return -1; int lenarr = arr.size(), minarr = *min_element(arr.begin(), arr.end()); vector<int> dp(aim, 0); int tmp; for (int i = ...

#include <string> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 解码 * @param nums string字符串 数字串 * @return int整型 */ int solve(string nums) { int len = nums.length(); vector<int> dp(len + 1, 0); //默认字符串第0位前还有一位 for (int i = 0; i <= len; i...

matrix本身就可以作为状态数组 #include <vector> class Solution { public: int minPathSum(vector<vector<int> >& matrix) { int n = matrix.size(), m = matrix[0].size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i * j) { matrix[i][j] += matrix[i - 1][j] > matrix[i...

#include <vector> class Solution { public: int minPathSum(vector<vector<int> >& matrix) { int n = matrix.size(), m = matrix[0].size(); vector<vector<int>> dp(matrix); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i * j) { dp[i][j] += dp[i - 1...

#include <vector> class Solution { public: int uniquePaths(int m, int n) { //计算组合数 if (m > n) { return uniquePaths(n, m); } double num = 1; for (int i = m + n - 2, j = m - 1; i >= n; i--, j--) { num = num * i / j; } return int(num); } // int uniquePaths(int m, int n) { //动态规划 // vector&l...

最长公共子序列的简化版本，字串要求必须连续。 #include <utility> #include <vector> class Solution { public: string LCS(string str1, string str2) { int len1 = str1.size(), len2 = str2.size(); vector<vector<int>> dp(len1, vector<int>(len2, 0)); int maxlen = 0; pair<int, int> maxindex; for...

学习了 #include <string> #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * longest common subsequence * @param s1 string字符串 the string * @param s2 string字符串 the string * @return string字符串 */ string LCS(string s1, string s2) { if (s1.size()*s2.size() =...

动态规划。一个小tip，将楼顶当作0花费楼梯加到cost数组和状态数组尾部，可以减少一点代码量。 #include <vector> class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int len = cost.size(); vector<int> dp(len + 1); // 状态数组 dp[0] = cost[0]; dp[1] = cost[1]; cost.push_back(0); // 楼顶 for (int i = 2; i <= ...

动态规划 #include <vector> class Solution { public: int jumpFloor(int number) { if(number<=2) return number; vector<int> dp(number); dp[0] = 1; dp[1] = 2; for (int i = 2; i < number; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[number - 1]; } };

记录一下 class Solution { public: int Fibonacci(int n) { int* dp = new int[n]; for (int i = 0; i < n; i++) { if (i == 0 || i == 1) { dp[i] = 1; } else { dp[i] = dp[i - 2] + dp[i - 1]; } } return dp[n - 1]; } };

感觉陷入思维定势了，一心想着怎么只用动态规划解题，没想到使用dfs+动态规划的结合方法。。。 class Solution { public: //记录四个方向 int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int n, m; //深度优先搜索，返回最大单元格数 int dfs(vector<vector<int> >& matrix, vector<vector<int> >& dp, int i, int j) { if (dp[i][j] != 0) return ...

思路：n的所有情况都是在n-1的基础上插入得来的，插入的方法就是从前往后一个个位置试，本来想着要加一个判断合法的函数，但后面思考了一下，只要保证插入的是"(...)"，即左括号在右括号左边的顺序，就一定合法。 class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; if (n == 0) { res.push_back(""); return res; } if (n == 1) { res.push_back...

采用图例中的递归方法。 #include <any> #include <set> #include <vector> class Solution { public: vector<string> Permutation(string str) { vector<string> res, tmpres; if (str.length() <= 1) { res.push_back(str); return res; } string tmp, cha; set<char> rec; // 设置一个集合，用于记录出现...