目录
47. 礼物的最大价值
题目描述
在一个 m*n 的棋盘的每一格都放有一个礼物，
每个礼物都有一定的价值（价值大于0）。
你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现一
class Solution1 {
public:
int maxValue(vector<vector<int>>& grid) {
int rowLen = (int)grid.size();
int colLen = (int)grid[0].size();
//dp[i][j] 表示走到 grid[i-1][j-i]位置拿到的最大礼物价值
vector<vector<int>> dp(rowLen+1,vector<int>(colLen+1,0));
//状态转移方程
//dp[i][j] = max(dp[j][i-1] dp[j-1][i]) + grid[i-1][j-1]
for (int row = 1; row<=rowLen; row++) {
for (int col = 1; col<=colLen; col++) {
int value1 = dp[row-1][col];
int value2 = dp[row][col-1];
dp[row][col] = max(value1, value2) + grid[row-1][col-1];
}
}
return dp[rowLen][colLen];
}
};
题目实现二
class Solution2 {
public:
int maxValue(vector<vector<int>>& grid) {
int rowLen = (int)grid.size();
int colLen = (int)grid[0].size();
for (int row = 1; row<=rowLen; row++) {
for (int col = 1; col<=colLen; col++) {
int value1 = row-2<0?0:grid[row-2][col-1];
int value2 = col-2<0?0:grid[row-1][col-2];
grid[row-1][col-1] = max(value1, value2) + grid[row-1][col-1];
}
}
return grid[rowLen-1][colLen-1];
}
};
题目实现三
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int rowLen = (int)grid.size();
int colLen = (int)grid[0].size();
vector<int> dp(colLen+1,0);
//状态转移方程
//dp[i][j] = max(dp[j][i-1] dp[j-1][i]) + grid[i-1][j-1]
for (int row = 1; row<=rowLen; row++) {
for (int col = 1; col<=colLen; col++) {
int value1 = dp[col];
int value2 = dp[col-1];
dp[col] = max(value1, value2) + grid[row-1][col-1];
}
}
return dp[colLen];
}
};
64. 最小路径和
题目描述
64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int rowLen = (int)grid.size();
int colLen = (int)grid[0].size();
vector<int>dp(colLen+1,INT_MAX);
for (int row = 1; row<=rowLen; row++) {
for (int col = 1; col<=colLen; col++) {
if (row == 1 && col == 1) {
dp[col] = grid[0][0];
continue;
}
int value1 = dp[col-1];
int value2 = dp[col];
dp[col] = min(value1, value2)+grid[row-1][col-1];
}
}
return dp[colLen];
}
};
62. 不同路径
题目描述
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n,1);
for (int row = 1; row<m; row++) {
for (int col = 1; col<n; col++) {
dp[col] = dp[col] + dp[col-1];
}
}
return dp[n-1];
}
};
121. 买卖股票的最佳时机
题目描述
121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释:
在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现-方式一
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
int minPrice = prices[0];
int maxValue = 0;
for (int i = 1; i<prices.size(); i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
}else{
maxValue = max(maxValue, prices[i] - minPrice);
}
}
return maxValue;
}
};
题目实现-方式二
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
for (int i = 1; i<prices.size(); i++) {
prices[i-1] = prices[i] - prices[i-1];
}
prices[prices.size()-1] = 0;
return maxContinueSubSeqSum(prices);
}
//计算最大连续子序列和
int maxContinueSubSeqSum(vector<int>& price){
//dp[i] 以price[i]结尾的最大连续子序列和
vector<int> dp(price.size());
dp[0] = price[0];
int maxValue = dp[0];
for (int i = 1; i<price.size(); i++) {
if (dp[i-1] > 0) {
dp[i] = dp[i-1] + price[i];
}else{
dp[i] = price[i];
}
maxValue = max(maxValue,dp[i]);
}
return maxValue;
}
};
72. 编辑距离
题目描述
72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现-方式一
class Solution {
public:
int minDistance(string word1, string word2) {
int w1Len = (int)word1.length();
int w2Len = (int)word2.length();
if (w1Len == 0 || w2Len == 0) return w1Len>w2Len?w1Len:w2Len;
//dp[i][j] word1[0,i-1] 到 word2[0,j-1]的最小操作步数
vector<vector<int>> dp(w1Len+1,vector<int>(w2Len+1,0));
for (int i = 0; i<=w1Len; i++) {
dp[i][0] = i;
}
for (int j = 0; j<=w2Len; j++) {
dp[0][j] = j;
}
for (int row = 1; row<=w1Len; row++) {
for (int col = 1; col<=w2Len; col++) {
int value1 = dp[row-1][col]+1;
int value2 = dp[row][col-1]+1;
int value3 = dp[row-1][col-1];
if (word1[row-1] != word2[col-1]) value3+=1;
dp[row][col] = min(min(value1,value2),value3);
}
}
return dp[w1Len][w2Len];
}
};
题目实现-方式二
class Solution {
public:
int minDistance(string word1, string word2) {
int w1Len = (int)word1.length();
int w2Len = (int)word2.length();
if (w1Len == 0 || w2Len == 0) return w1Len>w2Len?w1Len:w2Len;
//dp[i][j] word1[0,i-1] 到 word2[0,j-1]的最小操作步数
//优化成一维数组
vector<int> dp(w2Len+1,0);
for (int j = 0; j<=w2Len; j++) {
dp[j] = j;
}
for (int row = 1; row<=w1Len; row++) {
int cur = dp[0];
dp[0] = row;
for (int col = 1; col<=w2Len; col++) {
int value1 = dp[col]+1;
int value2 = dp[col-1]+1;
int value3 = cur;
cur = dp[col];
if (word1[row-1] != word2[col-1]) value3+=1;
dp[col] = min(min(value1,value2),value3);
}
}
return dp[w2Len];
}
};
5. 最长回文子串
题目描述
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现 - 暴力法
class Solution1 {
public:
string longestPalindrome(string s) {
int length = (int)s.length();
if (length == 0 || s.compare("") == 0) return s;
int left = 0;
int maxLength = 1;
for (int i = 0; i<length; i++) {
for (int j = i+1; j<length; j++) {
if (isPalindrom(s, i, j) && maxLength < j - i + 1) {
maxLength =j - i + 1;
left = i;
}
}
}
return s.substr(left,maxLength);
}
bool isPalindrom(string s,int left,int right){
while (left < right) {
if (s[left++] == s[right--]) continue;
return false;
}
return true;
}
};
题目实现 - 动态规划
class Solution2 {
public:
string longestPalindrome(string s) {
int length = (int)s.length();
if (length <= 1 ) return s;
// 最长回文子串的长度（至少是1）
int maxLength = 1;
// 最长回文子串的开始索引
int left = 0;
//dp[i][j] 代表s[i][j] 是否是回文串
vector<vector<bool>> dp(length,vector<bool>(length,true));
// 从下到上（i由大到小）
for (int i = length-1; i>=0; i--) {
// 从左到右（j由小到大）
for (int j = i; j<length; j++) {
// cs[i, j]的长度
int len = j - i + 1;
dp[i][j] = (s[i] == s[j] && (len<=2 || dp[i+1][j-1]));
if (dp[i][j] && maxLength < len){// 说明cs[i, j]是回文子串
left = i;
maxLength = len;
}
}
}
return s.substr(left,maxLength);
}
};
题目实现 - 扩展中心法
class Solution3 {
public:
//扩展中心法
string longestPalindrome(string s) {
int length = (int)s.length();
if (length <= 1 ) return s;
// 最长回文子串的长度（至少是1）
int maxLen = 1;
// 最长回文子串的开始索引
int begin = 0;
for (int i = length - 2; i >= 1; i--) {
// 以字符为中心向左右扩展
int len1 = palindromeLength(s, i - 1, i + 1);
// 以字符右边的间隙为中心向左右扩展
int len2 = palindromeLength(s, i, i + 1);
len1 =max(len1, len2);
if (len1 > maxLen) {
maxLen = len1;
begin = i - ((maxLen - 1) >> 1);
}
}
// 以0号字符右边的间隙为中心的最长回文子串长度是2
if (s[0] == s[1] && maxLen < 2) {
// cs[0, 1]就是最长的回文子串
begin = 0;
maxLen = 2;
}
return s.substr(begin,maxLen);
}
/**
* @return 从l开始向左、从r开始向右扫描，获得的最长回文子串的长度
*/
int palindromeLength(string cs, int l, int r) {
while (l >= 0 && r < cs.length() && cs[l] == cs[r]) {
l--;
r++;
}
return r - l - 1;
}
};
题目实现 - 扩展中心法2
class Solution {
public:
//扩展中心法2
string longestPalindrome(string s) {
int length = (int)s.length();
if (length <= 1 ) return s;
// 最长回文子串的长度（至少是1）
int maxLen = 1;
// 最长回文子串的开始索引
int begin = 0;
int i = 0;
while (i < length) {
int l = i - 1;
// 找到右边第一个不等于s[i]的位置
int r = i;
while (++r < length && s[r] == s[i]);
// r会成为新的i
i = r;
// 从l向左，从r向右扩展
while (l >= 0 && r < length && s[l] == s[r]) {
l--;
r++;
}
// 扩展结束后，cs[l + 1, r)就是刚才找到的最大回文子串
// ++l后，l就是刚才找到的最大回文子串的开始索引
int len = r - ++l;
if (len > maxLen) {
maxLen = len;
begin = l;
}
}
return s.substr(begin,maxLen);
}
};
题目实现 - 马拉车法
行者常至，为者常成！