class Solution { public: int rob(vector<int>& nums) { int len = nums.size(); vector<int> dp(len + 3, 0); //dp[i]代表以第i个为打劫的结尾的最大数额 for (int i = len - 2; i >= 0; i--) { //不选最后一个 dp[i] = nums[i] + max(dp[i + 2], dp[i + 3]); } ...

#include <vector> class Solution { public: int rob(vector<int>& nums) { int len = nums.size(); if (len == 1) return nums[0]; else { nums[1] = nums[0] > nums[1] ? nums[0] : nums[1]; for (int i = 2; i < nums.size(); i++) { ...

想复杂了，也想简单了。想复杂在于一开始没想到有这样一个动态规则，就想着字符串匹配那一套了；想简单在于只想着第一个字符串合起来去匹配，没想到“abba”“abxba”这类情况。 #include <vector> class Solution { public: int editDistance(string str1, string str2) { int len1 = str1.length(), len2 = str2.length(); vector<vector<int>>dp(len1 + 1, vect...

#include <vector> class Solution { public: bool isValid(const string& s) { if (s.empty() || s.length() > 3 || (s.length() > 1 && s[0] == '0')) { return false; } int num = 0; for (int i = 0; i < s.length(); i++) { ...

#include <utility> #include <vector> class Solution { public: string preprocess(const string& s) { //预处理字符串 string result = "^#"; //‘^’为开始标识符 for (char c : s) { result += c; result += "#"; //间隔插入‘#’号，将奇数和偶数长度的回文串统一为奇数长...

#include <vector> class Solution { public: int LIS(vector<int>& arr) { int len = arr.size(); if (!len) return len; vector<int> dp(len, 1); //记录以i位置结尾的最长上升子序列的长度 int res = 1, tmp; for (int i = 1; i < len; i++) { for (i...

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] - ...

#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&...

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

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...

#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...

#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; } ...

最长公共子序列的简化版本，字串要求必须连续。 #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; ...

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