- 力扣5 最长回文子序列【二维dp的代表】
- 力扣64 最小路径和【二维dp典型例题】
- 力扣1277 统计全为1的正方形子矩阵【二维dp典型例题】
- 力扣1035 不相交的线【二维dp应用题】
- 力扣72 编辑距离【二维dp应用题】
- 力扣1029 两地调度【二维dp应用题】
- 力扣518 零钱兑换II【一维dp应用题】
- 力扣174 地下城游戏 【二维dp应用题】
- 力扣96 不同的二叉搜索树【一维dp应用题】
- 力扣279 完全平方数【一维dp应用题】
- 力扣62 不同路径【二维dp应用题】
- 力扣63 不同路径II【二维dp应用题】
- 力扣264 丑数II【一维dp应用题】
- 力扣1246 删除回文子数组
- 力扣837 新21点
- 力扣70 爬楼梯
- 力扣871 最低加油次数
- 力扣523 连续的子数组和
动态规划简单的可以理解为用空间换时间的方法,它通过创建中间变量或是开辟一段存储空间,从而让程序在运行的过程中不必每次都从头开始计算,而是从中间变量和存储空间当中去处所需要的值。
力扣5 最长回文子序列【二维dp的代表】
废话不多说,先来一道 medium 试试身手
这道题很容易理解,就是找出字符串中最大的回文字符串,当然了我们使用暴力破解去枚举所有字串,但是这样做必然费时。那我们用一个dp表去记录已有结果然后推出当前结论。这里就是最巧面的地方了,怎么去找出已有结果和当前结果的关系呢?可以参考下图:
首先是最基本的表示法,和 base 情况:
再来是一般情况的示意图:
也就是当 J-I>=3的时候 我们要依赖之前记录的结果了
代码贴出来大家体会一下:
func longestPalindrome(s string) string {
l := len(s)
dp := make([][]bool, l)
for i := range dp {
dp[i] = make([]bool, l)
}
max := 1
maxStr := s[0:0]
for j := 1; j < l; j++ {
for i := 0; i < j; i++ {
if j-i < 3 {
dp[j][i] = s[i] == s[j]
} else {
dp[j][i] = (s[i] == s[j]) && dp[j-1][i+1]
}
if dp[j][i] {
if j-i+1 > max {
max = j - i + 1
maxStr = s[i : j+1]
}
}
}
}
return maxStr
}
C++的实现
状态转移方程:在i + 1 到 j - 1是回文的情况下,如果si和sj相等,则i到j一定是回文
边界条件
在下面的代码中,len可以理解为步长。下面的代码只是对以往的两次遍历然后反转字符串判断是否是回文的方法,以dp table的方法进行了优化,因此其时间复杂度还是O(n^2)
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
if(size <= 1)
return s;
vector<vector<int>>dp(size, vector<int>(size, 0));
string ret;
for(int len = 0; len < size; len++)
{
for(int i = 0; i + len < size; i++)
{
int j = i + len;
if(len == 0)
dp[i][j] = 1;
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] && j-i+1 > ret.size())
{
ret = s.substr(i, j - i + 1);
}
}
}
return ret;
}
};
力扣64 最小路径和【二维dp典型例题】
64. 最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-path-sum
这道题需要注意的是,这个方格不是正方形的方格
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
if(m == 0)
return 0;
int n = grid[0].size();
if(n == 0)
return 0;
for(int i = 1; i < m; i++)
grid[i][0] = grid[i - 1][0] + grid[i][0];
for(int j = 1; j < n; j++)
grid[0][j] = grid[0][j - 1] + grid[0][j];
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
return grid[m - 1][n - 1];
}
};
时间复杂度O(N ^ 2)
空间复杂度O(1)
力扣1277 统计全为1的正方形子矩阵【二维dp典型例题】
对于二维表的问题,通常可以创建另一张二维表来帮助解决问题,创建另外一张二维表的关键是需要明确创建表数据的顺序及与其前一个数据的关系,在一维列表中,如果我们是从左往右创建一维dp列表,需要知道的是新建的当前数据是这个数据之前的那些数据的关系,而在二维表中,如果是从左上角往右下角创建,则需要知道当前数据和这个数据左上角方向上的数据的关系,回到这道题来看,对于dp[i][j]则是查看其与dp[i-1][j], dp[i][j-1], dp[i-1][j-1]的关系。
1277. 统计全为 1 的正方形子矩阵
给你一个 m * n 的矩阵,矩阵中的元素不是 0 就是 1,请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1:
输入:matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出:15 解释: 边长为 1 的正方形有 10 个。 边长为 2 的正方形有 4 个。 边长为 3 的正方形有 1 个。 正方形的总数 = 10 + 4 + 1 = 15. 示例 2:
输入:matrix = [ [1,0,1], [1,1,0], [1,1,0] ] 输出:7
解释:
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
提示:
1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int row = matrix.size();
if(row == 0)
return 0;
int col = matrix[0].size();
if(col == 0)
return 0;
vector<vector<int>>A(row, vector<int>(col, 0));
A[0][0] = matrix[0][0];
int ret = A[0][0];
for(int i = 1; i < row; i++)
{
A[i][0] = matrix[i][0];
ret += A[i][0];
}
for(int j = 1; j < col; j++)
{
A[0][j] = matrix[0][j];
ret += A[0][j];
}
for(int i = 1; i < row; i++)
{
for(int j = 1; j < col; j++)
{
if(matrix[i][j] == 0)
A[i][j] = 0; //如果当前值为0则肯定无法构建成正方形
else
A[i][j] = 1 + min({A[i-1][j], A[i][j-1], A[i-1][j-1]});
ret += A[i][j];
}
}
return ret;
}
};
力扣1035 不相交的线【二维dp应用题】
这道题一开始我还真没想到是采用动态规划的方法去做,直到做不出的时候才隐约感到可能是动态规划,因为它可以形成一张二维表,而且对于当前值也是采用判断和之前值的方法来决定最终值是什么。最后看了看其他人的题解才明白应该如何去做。
1035. 不相交的线
我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在,我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线,只要 A[i] == B[j],且我们绘制的直线不与任何其他连线(非水平线)相交。
以这种方法绘制线条,并返回我们可以绘制的最大连线数。
示例 1:输入:A = [1,4,2], B = [1,2,4]
输出:2
解释:
我们可以画出两条不交叉的线,如上图所示。
我们无法画出第三条不相交的直线,因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。
示例 2:
输入:A = [2,5,1,2,5], B = [10,5,2,1,5,2]
输出:3
示例 3:
输入:A = [1,3,7,1,7,5], B = [1,9,2,5,1]
输出:2
提示:
1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/uncrossed-lines
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
d[i][j] 表示A的[0, i-1] 到 B的[0, j-1]的序列里最长公共子串,就是相等的最大长度
class Solution {
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
int sizeA = A.size();
int sizeB = B.size();
if(sizeA == 0 || sizeB == 0)
return 0;
vector<vector<int>>dp(sizeA + 1, vector<int>(sizeB + 1, 0));
for(int i = 1; i <= sizeA; i++)
{
for(int j = 1; j <= sizeB; j++)
{
dp[i][j] = A[i-1] == B[j - 1]? dp[i-1][j-1] + 1 : max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[sizeA][sizeB];
}
};
这位大神还给出了一维dp,我没有看懂,姑且先贴出来
def maxUncrossedLines(self, A, B):
m, n = len(A), len(B)
dp = [0] * (n + 1)
for i in xrange(m):
for j in range(n)[::-1]:
if A[i] == B[j]: dp[j+1] = dp[j] + 1
for j in range(n):
dp[j+1] = max(dp[j+1],dp[j])
return dp[n]
力扣72 编辑距离【二维dp应用题】
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’)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
public:
int minDistance(string word1, string word2) {
int size1 = word1.size();
int size2 = word2.size();
vector<vector<int>>dp(size1 + 1, vector<int>(size2 + 1, 0));
for(int i = 0; i < size1 + 1; i++)
dp[i][0] = i;
for(int j = 0; j < size2 + 1; j++)
dp[0][j] = j;
for(int i = 1; i < size1 + 1; i++)
{
for(int j = 1; j < size2 + 1; j++)
{
dp[i][j] = word1[i - 1] == word2[j - 1] ? dp[i-1][j-1] : 1 + min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]));
}
}
return dp[size1][size2];
}
};
基本上,只要列出动态规划的状态转移公式就可以正确的写出动态规划的代码。在这道题中,dp[i][j]表示到达i,j所产生的最小操作,那么到达dp[i][j]的路径有三种,dp[i-1][j], dp[i][j-1], dp[i-1][j-1],其中当word1[i] == word2[j]相等的时刻,从dp[i-1][j-1]到dp[i][j]不需要进行任何操作。这道题唯一需要注意的是在构建dp表的时候,需要特别的多增加一行和一列,作为处理边界。
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
if(m == 0 || n == 0)
return m + n;
int dp[m+1][n+1];
for(int i = 0; i < m + 1; i++)
dp[i][0] = i;
for(int j = 0; j < n + 1; j++)
dp[0][j] = j;
for(int i = 1; i < m + 1; i++)
{
for(int j = 1; j < n + 1; j++)
{
int left = dp[i][j-1];
int top = dp[i-1][j];
int left_top = dp[i-1][j-1];
if(word1[i-1] == word2[j-1])
left_top = left_top - 1;
dp[i][j] = 1+ min(left_top, min(left, top));
}
}
return dp[m][n];
}
};
力扣1029 两地调度【二维dp应用题】
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costs[i][1]。
返回将每个人都飞到某座城市的最低费用,要求每个城市都有 N 人抵达。
示例:
输入:[[10,20],[30,200],[400,50],[30,20]]
输出:110
解释:
第一个人去 A 市,费用为 10。
第二个人去 A 市,费用为 30。
第三个人去 B 市,费用为 50。
第四个人去 B 市,费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110,每个城市都有一半的人在面试。
提示:
1 <= costs.length <= 100
costs.length 为偶数
1 <= costs[i][0], costs[i][1] <= 1000
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-city-scheduling
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
int N = costs.size() / 2;
vector<vector<int>>dp(N+1, vector<int>(N+1, 0));
for(int i = 1; i <= N; i++)
dp[i][0] = dp[i-1][0] + costs[i-1][0];
for(int j = 1; j <= N; j++)
dp[0][j] = dp[0][j-1] + costs[j-1][1];
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
dp[i][j] = min(dp[i-1][j] + costs[i+j-1][0], dp[i][j-1] + costs[i + j - 1][1]);
}
return dp[N][N];
}
};
1.先假设全部飞到B市的话(并没有真的飞!!不是先到B再从B到A),再选择N人转飞到A市,那么这N个人的多花了price_A - price_B 的费用
2.因此最优的方案是,选出 price_A - price_B 最小的 NN 个人,让他们飞往 A 市,其余人飞往 B 市
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs, int res = 0) {
sort(costs.begin(), costs.end(), [](vector<int>&v1, vector<int>&v2){
return (v1[0] - v1[1] < v2[0] - v2[1]);
});
for(auto i = 0; i < costs.size() / 2; i++){
res += costs[i][0] + costs[i+costs.size()/2][1];
}
return res;
}
};
力扣518 零钱兑换II【一维dp应用题】
518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意:
你可以假设:
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/coin-change-2
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
动态规划的典型模版是
- 定义答案显而易见的基本情况。
- 制定根据简单的情况计算复杂情况的策略。
- 将此策略链接到基本情况。
在这道题中dp[i]表示的是在总数是i的情况下组合方案的个数。这是不能将从0到amount作为外循环,因为这样做的化,会较难排除掉重复的case
class Solution {
public:
int change(int amount, vector<int>& coins) {
if(amount == 0)
return 1;
if(coins.size() == 0)
return 0;
vector<int>dp(amount + 1, 0);
dp[0] = 1;
for(int i = 0; i < coins.size(); i++)
{
for(int j = coins[i]; j <= amount; j++)
{
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
时间复杂度:O(N x amount)。其中N为coins数组的长度
空间复杂度:O(amount),dp数组使用的空间
力扣174 地下城游戏 【二维dp应用题】
这道题我依旧没有解出来,在评论区有一个答案比较有意思,依旧采用的是二维dp的方法,不过它不是从左上角往右下角走,而是反过来,从右下角往左上角走。
dp表中除了找状态转移方程之外,还需要判断对于新添加的行和列的初始值应该是什么。在这套题中,新添加的行,通过赋值为INT_MAX来创建出护城河,令dp表不会选择护城河中的值,除非护城河中有特殊处理的值。
174. 地下城游戏
一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。
有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。
为了尽快到达公主,骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如,考虑到如下布局的地下城,如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下,则骑士的初始健康点数至少为 7。
-2 (K) -3 3
-5 -10 1
10 30 -5 (P)
说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/dungeon-game
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int row = dungeon.size();
int col = dungeon[0].size();
vector<vector<int>>dp(row + 1, vector<int>(col + 1, INT_MAX));
dp[row][col-1] = 1;
dp[row-1][col] = 1;
for(int i = row - 1; i >= 0; i--)
{
for(int j = col - 1; j >= 0; j--)
{
int need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
dp[i][j] = need > 0 ? need : 1;
}
}
return dp[0][0];
}
};
力扣96 不同的二叉搜索树【一维dp应用题】
96. 不同的二叉搜索树
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int numTrees(int n) {
int* dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++)
{
int tmp = 0;
for (int index = 0; index < i; index++)
{
tmp += (dp[index] * dp[i - index - 1]);
}
dp[i] = tmp;
}
return dp[n];
}
};
力扣279 完全平方数【一维dp应用题】
279. 完全平方数
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int numSquares(int n) {
if(n == 0)
return 0;
vector<int>square(n+1, INT_MAX);
square[0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j * j <= i; j++)
{
square[i] = min(square[i], square[i - j*j] + 1);
}
}
return square[n];
}
};
力扣62 不同路径【二维dp应用题】
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
例如,上图是一个7 x 3 的网格。有多少可能的路径?
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示:
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
当看到二维表格的时候,首先想到的就是构建二维dp表,找出各自之间的相互关系,这道题就解出来了。
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>>dp(m, vector<int>(n, 1));
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
return dp[m-1][n-1];
}
};
力扣63 不同路径II【二维dp应用题】
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明:m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
vector<vector<int>>dp(row, vector<int>(col, 0));
if(obstacleGrid[0][0] == 0)
dp[0][0] = 1;
else
return 0;
for(int i = 1; i < row; i++)
{
if(obstacleGrid[i][0] == 1)
{
for(int j = i; j < row; j++)
dp[j][0] = 0;
break;
}
else
{
dp[i][0] = 1;
}
}
for(int i = 1; i < col; i++)
{
if(obstacleGrid[0][i] == 1)
{
for(int j = i; j < col; j++)
dp[0][j] = 0;
break;
}
else
{
dp[0][i] = 1;
}
}
for(int i = 1; i < row; i++)
{
for(int j = 1; j < col; j++)
{
if(obstacleGrid[i][j] == 1)
dp[i][j] = 0;
else
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[row-1][col-1];
}
};
力扣264 丑数II【一维dp应用题】
264. 丑数 II
编写一个程序,找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题可以理解为是一维dp的应用题,在这里,下一个数的产生是和t2,t3,t5为下标的三个数所决定的,t2,t3,t5分别是用来乘2,乘3和乘5的。然后取出其中最小的那个数。
class Solution {
public:
int nthUglyNumber(int n) {
if(n <= 0)
return 0;
if(n == 1)
return 1;
int t2 = 0, t3 = 0, t5 = 0;
vector<int>k(n);
k[0] = 1;
for(int i = 1; i < n; i++)
{
k[i] = min(k[t2] * 2, min(k[t3] * 3, k[t5] * 5));
if(k[i] == k[t2] * 2) t2++;
if(k[i] == k[t3] * 3) t3++;
if(k[i] == k[t5] * 5) t5++;
}
return k[n-1];
}
};
力扣1246 删除回文子数组
1246. 删除回文子数组
给你一个整数数组 arr,每一次操作你都可以选择并删除它的一个 回文 子数组 arr[i], arr[i+1], …, arr[j]( i <= j)。
注意,每当你删除掉一个子数组,右侧元素都会自行向前移动填补空位。
请你计算并返回从数组中删除所有数字所需的最少操作次数。
示例 1:
输入:arr = [1,2]
输出:2
示例 2:
输入:arr = [1,3,4,1,5]
输出:3
解释:先删除 [4],然后删除 [1,3,1],最后再删除 [5]。
提示:
1 <= arr.length <= 100
1 <= arr[i] <= 20
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-removal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int minimumMoves(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for(int l = 1; l <= n; l++)
{
for(int i = 0, j = l - 1; j < n; i++, j++)
{
if(l == 1)
{
dp[i][j] = 1;
}
else
{
dp[i][j] = 1 + dp[i + 1][j];
if(i + 1 < n && arr[i] == arr[i + 1])
dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]);
for(int k = i + 2; k <= j; k++)
{
if(arr[i] == arr[k])
dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);
}
}
}
}
return dp[0][n - 1];
}
};
参考: https://www.tutorialspoint.com/palindrome-removal-on-cplusplus
力扣837 新21点
837. 新21点
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏,描述如下:
爱丽丝以 0 分开始,并在她的得分少于 K 分时抽取数字。 抽取时,她从 [1, W] 的范围中随机获得一个整数作为分数进行累计,其中 W 是整数。 每次抽取都是独立的,其结果具有相同的概率。
当爱丽丝获得不少于 K 分时,她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少?
示例 1:
输入:N = 10, K = 1, W = 10
输出:1.00000
说明:爱丽丝得到一张卡,然后停止。
示例 2:
输入:N = 6, K = 1, W = 10
输出:0.60000
说明:爱丽丝得到一张卡,然后停止。
在 W = 10 的 6 种可能下,她的得分不超过 N = 6 分。
示例 3:
输入:N = 21, K = 17, W = 10
输出:0.73278
提示:
0 <= K <= N <= 10000
1 <= W <= 10000
如果答案与正确答案的误差不超过 10^-5,则该答案将被视为正确答案通过。
此问题的判断限制时间已经减少。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/new-21-game
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
double new21Game(int N, int K, int W) {
if(K == 0 || N >= K + W)
return 1.0;
vector<double>dp(N + 1);
dp[0] = 1.0;
double Wsum = 1.0, res = 0.0;
for(int i = 1; i <= N; ++i)
{
dp[i] = Wsum / W;
if(i < K)
Wsum += dp[i];
else
res += dp[i];
if(i - W >= 0)
Wsum -= dp[i - W];
}
return res;
}
};
力扣70 爬楼梯
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
典型的动态规划的题,列出公式
step[n] = step[n-1] + step[n-2]
第n个台阶的可由第n-1台阶到达,也可以由第n-2阶台阶到达,因此第n阶的方法就是n-1阶的方法加上n-2阶的方法。
class Solution {
public:
int climbStairs(int n) {
if(n == 0 || n == 1 || n == 2)
return n;
vector<int>dp(n);
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i < n; i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
};
力扣871 最低加油次数
871. 最低加油次数
汽车从起点出发驶向目的地,该目的地位于出发位置东面 target 英里处。
沿途有加油站,每个 station[i] 代表一个加油站,它位于出发位置东面 station[i][0] 英里处,并且有 station[i][1] 升汽油。
假设汽车油箱的容量是无限的,其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。
当汽车到达加油站时,它可能停下来加油,将所有汽油从加油站转移到汽车中。
为了到达目的地,汽车所必要的最低加油次数是多少?如果无法到达目的地,则返回 -1 。
注意:如果汽车到达加油站时剩余燃料为 0,它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0,仍然认为它已经到达目的地。
示例 1:
输入:target = 1, startFuel = 1, stations = []
输出:0
解释:我们可以在不加油的情况下到达目的地。
示例 2:
输入:target = 100, startFuel = 1, stations = [[10,100]]
输出:-1
解释:我们无法抵达目的地,甚至无法到达第一个加油站。
示例 3:
输入:target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出:2
解释:
我们出发时有 10 升燃料。
我们开车来到距起点 10 英里处的加油站,消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后,我们从 10 英里处的加油站开到 60 英里处的加油站(消耗 50 升燃料),
并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。
我们沿途在1两个加油站停靠,所以返回 2 。
提示:
1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < … < stations[stations.length-1][0] < target
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-number-of-refueling-stops
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题将二维的问题用一维的dp表进行维护,是目前为止我第一次见到的方式。
class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
if(startFuel >= target)
return 0;
if(stations.size() == 0)
return -1;
vector<long>dp(stations.size() + 1, 0);
dp[0] = startFuel;
for(int i = 0; i < stations.size(); i++)
{
for(int t = i; t >=0; t--)
{
if(dp[t] >= stations[i][0])
dp[t+1] = max(dp[t+1], dp[t] + (long)stations[i][1]);
}
}
for(int i = 0; i < dp.size(); i++)
{
if(dp[i] >= target)
return i;
}
return -1;
}
};
力扣523 连续的子数组和
523. 连续的子数组和
给定一个包含 非负数 的数组和一个目标 整数 k ,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,且总和为 k 的倍数,即总和为 n * k ,其中 n 也是一个整数。
示例 1:
输入:[23,2,4,6,7], k = 6
输出:True
解释:[2,4] 是一个大小为 2 的子数组,并且和为 6。
示例 2:
输入:[23,2,6,4,7], k = 6
输出:True
解释:[23,2,6,4,7]是大小为 5 的子数组,并且和为 42。
说明:
数组的长度不会超过 10,000 。
你可以认为所有数字总和在 32 位有符号整数范围内。
ui
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/continuous-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这套题可以采用前缀和的方式来减少计算量,其实现如下方的代码,但是其依旧会超时
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int size = nums.size();
vector<int>preSum(size + 1, 0);
preSum[0] = 0;
for(int i = 0; i < size; i++)
{
preSum[i + 1] = preSum[i] + nums[i];
}
for(int left = 0; left < size - 1; left++)
{
for(int right = left + 1; right < size; right++)
{
int sum = preSum[right + 1] - preSum[left];
if(sum == k || (k != 0 && sum % k == 0))
return true;
}
}
return false;
}
};
下面的是采用hashtable存储余数的方式,如果在之后的sum中有存在的余数,那么证明拥有这样的和
使用哈希表保存到下标 ii 个止的元素的和,并且 对这个前缀和除以 kk 取余数(请大家思考这是为什么?)。
原因如下:遍历输入数组,记录到当前位置为止的 sum%ksum,一旦我们找到新的 sum%ksum 的值(即在哈希表中没有这个值),我们就 往哈希表中插入一条记录 key:sum % k,value:i。
假设第 ii 个位置的 sum % ksum 的值为 remrem。如果以 ii 为左端点的任何子数组的和是 kk 的倍数,假设该位置为 jj ,那么哈希表中第 jj 个元素保存的值为 (rem + nk)\%k(rem+n∗k)%k ,其中 n > 0n>0 整数。发现 (rem + nk)\%k = rem(rem+n∗k)%k=rem ,也就是跟第 ii 个元素保存到哈希表 中的值相同。
基于这一观察,可以得出结论:
无论何时,只要 sum%ksum 的值已经被放入哈希表,代表着有两个下标 ii 和 jj ,它们之间元素的和是 kk 的整数倍。因此只要哈希表中有相同的 sum\%ksum%k ,就可以直接返回 \teat{True} 。
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int sum = 0;
map<int, int> remainSum;
remainSum[0] = -1;
int size = nums.size();
for(int i = 0; i < size; i++)
{
sum += nums[i];
if(k != 0)
sum = sum % k;
if(remainSum.find(sum) != remainSum.end())
{
if(i - remainSum[sum] > 1)
return true;
}
else
{
remainSum[sum] = i;
}
}
return false;
}
};