这一个dp理解一开始有点问题，搞乱了。应该理解成相应长度比较好！ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ int editDistance(string str1, string str2) { int len1 = str1.size(), len2 = str2.size(); // dp[i][j] 表示到 str1[i] str2[j] 为止的需要的最...

隔了几天没写，唉思路速度都跟不上。果然这东西就是不能停 class Solution { public: /** * * @param s string字符串 * @return string字符串vector */ vector<string> restoreIpAddresses(string s) { std::vector<std::string> res; // 找出三个点可能的位置三重循环暴力查找 int length = s.size(); // 注意是左闭右开，所以每一层指向的永远是下一层的第一个数字 // 注意循环范围是 < 同样要考虑右开这一因...

这道题我不理解，也不了解manacher算法。先这样吧，回头再看不浪费时间了。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A string字符串 * @return int整型 */ int getLongestPalindrome(string A) { int length = A.size(); // 源字符串全部变为偶数个字符，加上头两位。最后有指向回文串最右一位的下一位，故组合出来的字符串实际个数为偶数个 std::vector<int> mp(2 * ...

群里网友在讨论，自己也简单思考了一下，确实容易混乱

渐渐对动态规划有感觉了 class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { // dp[i] 表示结尾元素为i下标的子数组的和的最大值 // 最后一个不一定就是和最大值，因为子数组不一定取到最后一个元素 // 每次取子数组时，记录下最大值 int res = -200; std::vector<int> dp(array.size(), 0); // 假设每个元素都为子数组时和最大 for (int i = 0; i < array.size(); ++i) { d...

不是很理解这个，再看看 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& arr) { if (arr.empty()) { return 0; } // dp[i] 表示到下标i结尾（包括元素i）的字符串的最长严格上升子序列长度 int res = 0; std::vector<int> d...

类似背包但又不是背包，涨知识了 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 最少货币数 * @param arr int整型vector the array * @param aim int整型 the target * @return int整型 */ int minMoney(vector<int>& arr, int aim) { // 为0，无需货币 if (aim <= 0) { return 0; } // 不为0，但是钱包为空，无解 if (arr.emp...

考虑边界条件（鲁棒性） class Solution { public: /** * 解码 * @param nums string字符串 数字串 * @return int整型 */ int solve(string nums) { // dp[i] 表示长度为 i 的字符串有 多少种可能译码结果 if (nums.empty() || nums[0] == '0') { return 0; } int size = nums.size(); for (int i = 1; i < size; ++i) { if (nums[i] == '0') { if (nums[i - 1] !...

开始慢慢习惯这种题目 class Solution { public: /** * * @param matrix int整型vector<vector<>> the matrix * @return int整型 */ int minPathSum(vector<vector<int> >& matrix) { int row = matrix.size(), col = matrix[0].size(); // dp[i][j] 代表i*j大小矩阵的最大路径和 std::vector<std::vector<int>&...

数学解法不是很理解，能够画出来式子，但是转化为代码计算不是很理解 class Solution { public: /** * * @param m int整型 * @param n int整型 * @return int整型 */ // 到达最后一个结点有两种方式，一个向下一个向右这两种 // 使用递归从后面往前推容易理解 // 使用动态规划 // 运用数学 --> 最优解 int uniquePaths(int m, int n) { // 递归思路 if (m == 1 || n == 1) { return 1; } // 分别是开头向右走和向下走的结果之和 return uni...

字串和子序列不同，一旦中间一个不等，其当前长度最长公共字串就要变为0. 同时记录下公共字串的最大值以及对应的字符串末尾下标。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ // 字串要求字符在源对象中连续，而序列只保证相对顺序不变 string LCS(string...

这道题对我有点难度哈。 dp状态转移方程怎么确认？怎么根据dp状态转移进行字符串还原？ 这道题的难点 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.empty() ||...

跳台阶的变种，加入了代价，需要计算最优 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cost int整型vector * @return int整型 */ int minCostClimbingStairs(vector<int>& cost) { // dp[i] 表示在该台阶之前的最小花费 std::vector<int> dp(cost.size() + 1, 0); dp[0] = dp[1] = 0; // 当前台阶，可由前一级台阶跳一...

没啥好说的，递归和动态规划的入门。 开始刷动态规划了。 class Solution { public: int Fibonacci(int n) { int fir = 0, sec = 1, res = 1; for (int i = 2; i <= n; ++i) { res = fir + sec; fir = sec; sec = res; } return res; } };