代码拉取完成，页面将自动刷新
矩阵 (10%)
序列(40%)
双序列(40%)
Leetcode 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
n-1个台阶处+1阶或在n-2个台阶处+2阶n-1和n-2个台阶相关，dp[n]=dp[n-1]+dp[n-2]
int climbStairs(int n) {
vector<int> dp;
for(int i = 0; i <= n; ++i){
if (i == 0) wayNums.push_back(1);
else if (i==1) wayNums.push_back(2);
else wayNums.push_back(dp[i - 1] + dp[i - 2]);
}
return dp.back();
}
leetcode给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
bool canJump(vector<int>& nums) {
vector<bool> dp(nums.size(), false);
dp[0] = true;
for (int i = 1; i < nums.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (dp[j] == true && nums[j] >= i - j) {
dp[i] = true;
break;
}
}
}
return dp[nums.size()-1];
}
leetcode给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
int jump(vector<int>& nums) {
vector<int> dp(nums.size(),0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; i < nums.size(); ++i) {
int less = 0x3f3f3f3f;
for (int j = i-1; j >= 0; --j) {
if (j + nums[j] >= i) {
less = min(less, dp[j] + 1);
}
}
dp[i] = less;
}
return dp[nums.size()-1];
}
int jump(vector<int>& nums) {
vector<int> dp(nums.size(),0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; i < nums.size(); ++i) {
int j = 0;
while (j < nums.size() && j + nums[j] < i) j++;
dp[i] = dp[j] + 1;
}
return dp[nums.size()-1];
}
leetcode给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回符合要求的最少分割次数。
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
dp[i]的值与dp[i-1]、dp[i-2].....有怎么的联系i之前的所有下标j，找到所有能和i组成回文串的j下标，在这么多能和i组成的回文串的j下标中，通过比较找出最少分割数的dp[j],再+1就是当前位置dp[i]的值. int minCut(string s) {
vector<int> dp(s.size(), 0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; s[i] != '\0'; ++i) {
if (isPalindrome(s, 0, i)){
dp[i] = 0;
continue;
}
for (int j = i; j >= 0; --j){
if (isPalindrome(s, j, i)){
dp[i] = min(dp[i], dp[j-1] + 1);
}
}
}
return dp[s.size()-1];
}
bool isPalindrome(string s, int left, int right) {
if(right == left) return true;
while (left < right) {
if (s[left] != s[right]) return false;
left++, right--;
}
return true;
}
Leetcode 计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 在不触动警报装置的情况下，能够偷窃到的最高金额。
i-1户，就不能抢劫第i户，或者是i-2户再加上当前户i
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);nums[0]和max(nums[0].nums[1])
int rob(vector<int>& nums) {
if(!nums.size()) return 0;
vector<int> dp;
for(int i = 0; i < nums.size(); i++){
if (i == 0) dp.push_back(nums[0]);
else if (i == 1) dp.push_back(max(nums[0], nums[1]));
else dp.push_back(max(dp[i - 1], dp[i - 2] + nums[i]));
}
return dp.back();
}
所有的房屋都围成一圈.
Leetcode
0~n-2
1~n-1
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
return max(rob(nums, 0, nums.size()-2),rob(nums, 1, nums.size()-1));
}
int rob(vector<int>&nums, int left, int right){
//根据left和right确定开辟dp数组的大小
int cnt = left - right + 1;
vector<int> dp;
//cur是dp数组的下标，不是nums的下标，cur从0，即dp的第一元素开始
for(int cur = 0; cur < cnt; cur++){
if (cur == 0) dp.push_back(nums[left]);
else if (cur ==1) dp.push_back(max(nums[left], nums[left + 1]));
else{//max里比的是dp数组里的值，不是nums数组的
dp.push_back(max(dp[cur - 1], dp[cur - 2] + nums[left + cur]));
}
}
return dp.back();
}
Leetcode在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
int rob(TreeNode* root) {
if (root = NULL) return 0;
int money = root->val;
if(root->left) money += rob(root->left->left) + rob(root->left->right);
if(root->right) money += rob(root->right->left) + rob(root->right->right);
return max(money, rob(root->left) + rob(root->right));
}
int rob(TreeNode* root) {
unordered_map<TreeNode*, int>dp;
return rob(root, dp);
}
int rob(TreeNode* root, unordered_map<TreeNode*, int> dp){
if (root == NULL) return 0;
if (dp.count(root) != 0) return dp[root];
int money=root->val;
if (root->left) money += rob(root->left->left, dp) + rob(root->left->right, dp);
if (root->right) money += rob(root->right->left, dp) + rob(root->right->right, dp);
int res = max(money,rob(root->left,dp) + rob(root->right, dp));
dp[root] = res;
return res;
}
int rob(TreeNode* root) {
vector<int> res(2);
res = postOrder(root);
return max(res[0], res[1]);
}
vector<int> postOrder(TreeNode* root){
if (root == NULL) return {0,0};
vector<int> res(2);
vector<int> left = postOrder(root->left);
vector<int> right = postOrder(root->right);
res[0] = max(left[0], left[1]) + max(right[0], right[1]);
res[1] = root->val + left[0] + right[0];
return res;
}
leetcode给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
dp[i][j] = min(dp[i-1][j] + dp[i-1][j]) + triangle[i][j]
0-1的元素;还有每一行的最后一个第i元素，他的上一行只有i-1这个元素。 int minimumTotal(vector<vector<int>>& triangle) {
int len = triangle.size();
vector<vector<int>> dp(len,vector<int>(len,0x3f3f3f3f));
dp[0][0] = triangle[0][0];
for (int i = 1; i < len; ++i) {
for (int j = 0; j < triangle[i].size(); ++j) {
if (j == 0) dp[i][j] = dp[i-1][j] + triangle[i][j];
else if (j == i) dp[i][j] = dp[i-1][j-1] + triangle[i][j];
else dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
}
}
sort(dp[len-1].begin(), dp[len-1].end());
return dp[len-1][0];
}
dp[i][j] = min(dp[i+i][j], dp[i+1][j]) + triangle[i][j]
int minimumTotal(vector<vector<int>>& triangle) {
// 自底向上
// 从倒数第二行开始
for (int i = triangle.size() - 2; i >= 0; --i) {
for (int j = 0; j < triangle[i].size(); ++j) {
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
}
}
return triangle[0][0];
}
leetcode给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
vector<vector<int>> dp(row, vector<int>(col, 0x3f3f3f3f));
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (i == 0 && j > 0) dp[i][j] = dp[i][j-1] + grid[i][j];
else if (j == 0 && i > 0) dp[i][j] = dp[i-1][j] + grid[i][j];
else if (i == 0 && j == 0) dp[i][j] = grid[0][0];
else dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[row-1][col -1];
}
grid[i][j] += min(grid[i+1][j], grid[i][j+1]);
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
for (int i = row-1; i >= 0; --i) {
for (int j = col-1; j >= 0; --j) {
if (i == row-1 && j == col-1) continue;
else if (i == row-1) grid[i][j] += grid[i][j+1];
else if (j == col-1) grid[i][j] += grid[i+1][j];
else grid[i][j] += min(grid[i+1][j], grid[i][j+1]);
}
}
return grid[0][0];
}
leetcode一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,0x3f3f3f3f));
for (int i = m-1; i >=0; --i) {
for (int j = n-1; j >= 0; --j) {
if (i == m-1 && j == n-1) dp[i][j] = 1;
else if (i == m-1) dp[i][j] = dp[i][j+1];
else if (j == n-1) dp[i][j] = dp[i+1][j];
else dp[i][j] = dp[i+1][j] + dp[i][j+1];
}
}
return dp[0][0];
}
leetcode一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
dp[i][j] = dp[i+1][j] + dp[i][j+1];
dp[i][j] = dp[i+1][j];,最后一行的格子dp[i][j] = dp[i][j+1];
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
vector<vector<long>> dp(row,vector<long>(col,0x3f3f3f3f));
for (int i = row-1; i >=0; --i) {
for (int j = col-1; j >= 0; --j) {
if (obstacleGrid[i][j] == 1) {dp[i][j] = 0; continue;}
if (i == row-1 && j == col-1) dp[i][j] = 1;
else if (i == row-1) dp[i][j] = dp[i][j+1];
else if (j == col-1) dp[i][j] = dp[i+1][j];
else dp[i][j] = dp[i+1][j] + dp[i][j+1];
}
}
return dp[0][0];
}
leetcode给定一个无序的整数数组，找到其中最长上升子序列的长度。
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
dp[i] = max(dp[j], dp[j-1].......） + 1 其中j表示i之前的所以元素。nums[j] < nums[i] 才行。dp[nums.size()-1]，而是dp数组中的最大值，因为dp[i]代表的是以nums[i]为序列结尾的最长个数。实际最长的序列不一定是以最后一个数字nums[size()-1]为结尾的。max_element()在头文件 #include <algorithm> 中，返回的是迭代器，所以输出值的话要在前面加 *,默认是从小到大排列. int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size() , 1);
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
leetcode给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明： 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
leetcode给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。 若这两个字符串没有公共子序列，则返回 0。
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
dp[i][j]表示：对于 s1[1..i] 和 s2[1..j]，它们的 LCS 长度是 dp[i][j]。dp[i][j] = (dp[i-1][j], dp[i][j-1], dp[i-1][j-1)
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.size();
int len2 = text2.size();
vector<vector<int> > dp(len1 + 1, vector<int>(len2 + 1, 0));
for (int i = 1; i < len1 + 1; ++i) {
for (int j = 1; j < len2 + 1; ++j) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[len1][len2];
}
leetcode给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
word1变为word2,也就是用删除，增加，替换操作将word1的每个字母变成word2的字母word1 为空变成 word2 最少步数，就是插入操作word2 为空，需要的最少步数，就是删除操作 int minDistance(string word1, string word2) {
int len1 = word1.size();
int len2 = word2.size();
vector<vector<int> > dp(len1 + 1, vector<int>(len2 + 1, 0));
for (int i = 0; i < len1 + 1; ++i) {
dp[i][0] = i;
}
for (int i = 0; i < len2 + 1; ++i) {
dp[0][i] = i;
}
for (int i = 1; i < len1 + 1; ++i) {
for (int j = 1; j < len2 + 1; ++j) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
}
return dp.back().back();
}
leetcode给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (auto coin : coins) {
if (i < coin) continue;
dp[i] = min(dp[i], dp[i-coin] + 1);
}
}
return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount];
}
leetcode 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j] 表示从第i个字符开始到第j个字符结束len = 0 开始遍历建立dp数组。 string longestPalindrome(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n ,false));
string res;
int MAX = INT_MIN;
for (int len = 0; len < n; ++len) {
for (int i = 0; i + len < n; ++i) {
int j = i + len;
if (len == 0) dp[i][j] = true;
else if (len == 1) dp[i][j] = (s[i] == s[j]);
else dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
if (dp[i][j] && len + 1 > MAX) {
MAX = len + 1;
res = s.substr(i, len + 1);
}
}
}
return res;
}
小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。 出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
输入：leaves = "rrryyyrryyyrr"
输出：2
解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"
int minimumOperations(string leaves) {
int n = leaves.size();
vector<vector<int>> dp(3, vector<int>(n));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < n; ++j) {
dp[i][j] = 0x3f3f3f3f;
}
}
dp[0][0] = leaves[0] == 'r' ? 0 : 1;
for (int i = 1; i < n; ++i) {
dp[0][i] = dp[0][i - 1] + (leaves[i] == 'y' ? 1 : 0);
dp[1][i] = min(dp[0][i - 1], dp[1][i - 1]) + (leaves[i] == 'r' ? 1 : 0);
dp[2][i] = min(dp[1][i - 1], dp[2][i - 1]) + (leaves[i] == 'y' ? 1 : 0);
}
return dp[2][n - 1];
}
leetcode 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp[n][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
0<=i<=N, 0<=j<=W
dp[0][0...W]初始化为0，表示将前0个物品（即没有物品）装入书包的最大价值为0。那么当 i > 0 时dp[i][j]有两种情况：
dp[i−1][j]；
dp[i−1][j−w[i]] + v[i]
dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]) // j >= w[i]
for (int i = 1; i <= N; i++) {
for (int j = W; j >= 0; j--) {
if (j >= w[i]) { /// 如果背包装得下当前的物体
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
} else { /// 如果背包装不下当前物体
dp[i][j] = dp[i-1][j];
}
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。