如何查看网站服务器类型,网站二维码怎么做的,海南在线一家,微信广告服务商平台让我们开始#xff1a;动态规划#xff01; 70. 爬楼梯 - 力扣#xff08;LeetCode#xff09;
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
class Solution {
public:int climbStairs(i…让我们开始动态规划 70. 爬楼梯 - 力扣LeetCode
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
class Solution {
public:int climbStairs(int n) {vectorint dp(n1);if(n0)return 0;if(n1)return 1;dp[1]1,dp[2]2;for(int i3;in;i){dp[i]dp[i-1]dp[i-2];}return dp[n];}
};
动态规划是客观地说最注重逻辑的题型因为我们必须要找到由子问题推导到主问题的这个过程才可以做。爬楼梯的这个逻辑是什么呢当我们i来到3以后我们就可以把爬三阶楼梯拆分成爬一个二阶三减一的楼梯方法加一次爬一阶和爬一个一阶三减二的楼梯加一次爬两阶同理四阶就是一个爬一个三阶的楼梯方法加一次一步和爬二阶的楼梯方法加一次两步。
746. 使用最小花费爬楼梯 - 力扣LeetCode
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int ncost.size();vectorint dp(n1);if(n0)return 0;if(n1)return cost[0];dp[0]0;dp[1]0;for(int i2;in;i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[n];}
};
这个题的递推的关键在于找到最小花费我们需要考量爬到i阶楼梯的最小花费由于每次只能爬一阶或者二阶所以我们只需要往前找一阶的最小花费加上该阶的花费与往前两阶的最小花费与该阶的花费即可。
62. 不同路径 - 力扣LeetCode
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m1,vectorint(n1));for(int i1;im;i){dp[i][1]1;}for(int j1;jn;j){dp[1][j]1;}for(int i2;im;i){for(int j2;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m][n];}
};
二维动态规划的例题这里的dp[i][j]代表的意思是i*j的网格到终点的路径数如果是一行或者一列的话都是1然后第i行j列等同于从i-1行j列的路径数与i行j-1列的路径数的总和。
63. 不同路径 II - 力扣LeetCode
给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角即 grid[0][0]。机器人尝试移动到 右下角即 grid[m - 1][n - 1]。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {if(obstacleGrid.empty()||obstacleGrid[0][0]1)return 0;int mobstacleGrid.size(),nobstacleGrid[0].size();vectorvectorint dp(m,vectorint(n));dp[0][0]1;for(int i1;im;i){if(obstacleGrid[i][0]0dp[i-1][0]!0)dp[i][0]1;else dp[i][0]0;}for(int j1;jn;j){if(obstacleGrid[0][j]0dp[0][j-1]!0)dp[0][j]1;else dp[0][j]0;} for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i][j]0){dp[i][j]dp[i-1][j]dp[i][j-1];}else dp[i][j]0;}}return dp[m-1][n-1];}
};
这个题无疑要麻烦得多因为障碍物的出现我们必须随时检查障碍物是否存在。除此之外和正常的不同路径区别不大注意边界条件的处理以及网格的下标与我们动态数组的下标的对应关系。
343. 整数拆分 - 力扣LeetCode
给定一个正整数 n 将其拆分为 k 个 正整数 的和 k 2 并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
class Solution {
public:int integerBreak(int n) {vectorint dp(n1);dp[2]1;for(int i3;in;i){for(int j1;ji/2;j){dp[i]max(dp[i],max(dp[i-j]*j,(i-j)*j));}}return dp[n];}
};
这个题虽然结果看起来似乎非常简单但其中涉及到的思路其实挺复杂。这里dp[i]主要考虑了三种情况dp[i]本身dp[i-j]*j整数i-j的最大乘积乘以j(i-j)*j整数i-j乘以j来考虑整数i的最大乘积j利用了乘法的性质可以少遍历一半的区间。
96. 不同的二叉搜索树 - 力扣LeetCode
给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。
class Solution
{
public:int numTrees(int n) {vectorint f(n1,0);f[0]1;f[1]1;for(int i2;in;i){for(int j1;ji;j){f[i]f[i-j]*f[j-1];}}return f[n];}
};
这里我就不用自己的话赘述了。直接上图吧
本质上是一个找规律并表达出来的问题。
46. 携带研究材料第六期模拟笔试 (kamacoder.com)
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。
小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。
#include iostream
#include vector
using namespace std;
int main(){int n,zooms;cinnzooms;vectorint weights(n);vectorint values(n);for(int i0;in;i){cinweights[i];}for(int i0;in;i){cinvalues[i];}vectorvectorint dp(n1,vectorint(zooms1,0));for(int jweights[0];jzooms;j){dp[0][j]values[0];}for(int i1;in;i){for(int j0;jzooms;j){if(jweights[i])dp[i][j]dp[i-1][j];else dp[i][j]max(dp[i-1][j],dp[i-1][j-weights[i]]values[i]);}}coutdp[n-1][zooms]endl;return 0;
}
0-1背包作为动态规划的经典题目可以说非常重要难点其实主要在于对dp数组的理解以及初始化的过程要做到每一步在干嘛心中有数才可以。
#include iostream
#include vector
using namespace std;
int main(){int n,zooms;cinnzooms;vectorint weights(n);vectorint values(n);for(int i0;in;i){cinweights[i];}for(int i0;in;i){cinvalues[i];}vectorint dp(zooms1,0);for(int i0;in;i){for(int jzooms;jweights[i];--j){dp[j]max(dp[j],dp[j-weights[i]]values[i]);}}coutdp[zooms]endl;return 0;
}
在这里放上第二种做法将二维数组dp转换为一维数组从背包空间容量大小开始从上往下遍历分别得到最大的价值。值得一提的是一维的动态规划数组一定不能正向遍历因为这会反复调用已经被确认的dp数组里的值变成完全背包问题。
416. 分割等和子集 - 力扣LeetCode
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
class Solution {
public:bool canPartition(vectorint nums) {int sumaccumulate(nums.begin(), nums.end(), 0);if(sum%2!0)return false;int targetsum/2;vectorint dp(target1);for(int i0;inums.size();i){for(int jtarget;jnums[i];--j){dp[j]max(dp[j],dp[j-nums[i]]nums[i]);}}return dp[target]target;}
};
这是一个典型的0-1背包应用题我们要判断能否分割成两个和相等的子集其实就是判断我们能否填满容量为数组总和一半的背包就变成了我们的0-1背包问题这里我们的物体的容量和价值相同都是nums[i]。
1049. 最后一块石头的重量 II - 力扣LeetCode
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。
class Solution {
public:int lastStoneWeightII(vectorint stones) {int nstones.size();vectorint dp(15001,0);int sumaccumulate(stones.begin(), stones.end(), 0);int targetsum/2;for(int i0;in;i){for(int jtarget;jstones[i];--j){dp[j]max(dp[j],dp[j-stones[i]]stones[i]);}}return sum-dp[target]-dp[target];}
};
这个题其实和上个题类似也是找能否填满容量为数组总和的一半的背包问题不过这个题不用返回是否而是返回最小的差值具体来说只是return 的东西不太一样。
494. 目标和 - 力扣LeetCode
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sumaccumulate(nums.begin(), nums.end(), 0);if((targetsum)%2!0)return 0;int left(targetsum)/2;vectorint dp(left1,0);dp[0]1;for(int i0;inums.size();i){for(int jleft;jnums[i];--j){dp[j]dp[j-nums[i]];}}return dp[left];}
};
这个题其实比想象中还要难理解对于这个题而言可能真正的难点在于如何将问题转换为背包问题我将视频链接放在这里。动态规划之背包问题装满背包有多少种方法| LeetCode494.目标和_哔哩哔哩_bilibili
474. 一和零 - 力扣LeetCode
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素集合 x 是集合 y 的 子集 。
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1,vectorint(n1,0));for(string str:strs){int oneNum0,zeroNum0;for(char c:str){if(c0)zeroNum;else oneNum;}for(int im;izeroNum;--i){for(int jn;joneNum;--j){dp[i][j]max(dp[i][j],dp[i-zeroNum][j-oneNum]1);}}}return dp[m][n];}
};
这个题其实是一个比较经典的0-1背包问题只是将物品的序号由一个一维的数组变成了一个二维的数组这就比较考察我们对0-1背包的基本理解了。这题比较容易犯错的地方在于最后的递推公式中的加一因为这里我们的dp数组的含义是最多包含m个0和n个1的string的最大子集个数所以我们只能加一用0-1背包类比的话就是所有的物品的value都是1。
52. 携带研究材料第七期模拟笔试 (kamacoder.com)
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的重量并且具有不同的价值。
小明的行李箱所能承担的总重量是有限的问小明应该如何抉择才能携带最大价值的研究材料每种研究材料可以选择无数次并且可以重复选择。
#include iostream
#include vector
using namespace std;
int main(){int n,badgeweights;cinnbadgeweights;vectorint weights(n1);vectorint values(n1);for(int i0;in;i){cinweights[i]values[i];}vectorint dp(badgeweights1,0);for(int i0;in;i){for(int j0;jbadgeweights;j){if(weights[i]j){dp[j]max(dp[j],dp[j-weights[i]]values[i]);}}}coutdp[badgeweights]endl;return 0;
}
这个就属于完全背包的问题了所谓完全背包就是在0-1背包的基础上物品可以无限选择主要带来的改动就是在遍历的过程中我们可以采取两个从小到大的遍历了因为覆盖原来的值也无所谓。
518. 零钱兑换 II - 力扣LeetCode
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数
class Solution {
public:int change(int amount, vectorint coins) {vectoruint64_t dp(amount1,0);dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
};
与目标和类似的一题但是把背包替换成了完全背包两题的递推公式是一样的dp[j]dp[j-nums[i]];但是问题在于对背包的遍历对于0-1背包我们一般从后往前遍历因为对于dp数组中的数来说他们的值的变化依据来自于表左上方也就是当前序号之前的值如果从前往后遍历容易反复使用但对于完全背包来说我们无所谓反复使用甚至可以说需要反复使用所以完全背包就是从前往后遍历。
377. 组合总和 Ⅳ - 力扣LeetCode
给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorunsigned long long dp(target 1, 0); // 使用更大的类型以防止溢出dp[0] 1; // 只有当目标值为0时有一种方法即不选择任何数for (int j 1; j target; j) { // 遍历所有可能的目标值for (int i 0; i nums.size(); i) { // 遍历所有可能的数字if (j nums[i]) { // 确保不会访问负索引dp[j] dp[j - nums[i]];}}}return dp[target];}
};
这个题与上述的完全背包求组合数又不一样这个题求的是排列数所谓组合和排列的区别只在于有无顺序而反应在题目中最大的区别就在于是先遍历物品还是先遍历背包。我们不妨这样想如果我们先遍历物品我们是根据物品填背包物品是首先被考虑的那么什么时候放进背包就不重要了这就是组合反之我们先遍历背包是根据背包来选物品那么这个时候我们先放哪个物品进去都会对后续的背包选择物品产生影响这就是排列。
57. 爬楼梯第八期模拟笔试 (kamacoder.com)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
#include iostream
#include vector
using namespace std;
int main(){int n,weights;cinnweights;vectorint dp(n1,0);dp[0]1;for(int j1;jn;j){for(int i1;iweights;i){if(ij){dp[j]dp[j-i];}}}coutdp[n]endl;return 0;
}
又是一个求排列的题并无太多特殊之处。
322. 零钱兑换 - 力扣LeetCode
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount1,INT_MAX);dp[0]0;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){if(dp[j-coins[i]]!INT_MAX){dp[j]min(dp[j],dp[j-coins[i]]1);}}}if(dp[amount]INT_MAX)return -1;else return dp[amount];}
};
这个题和之前的要求又反过来了要求最少的硬币数量所以我们的递推公式需要变成求min除此之外我们还要注意我们的初始化条件dp[0]0,在这里dp的意义是最少的硬币数所以我们针对0元的最少硬币自然是0
279. 完全平方数 - 力扣LeetCode
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { // 遍历背包for (int j 1; j * j i; j) { // 遍历物品dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];}
};
其实也是个经典的完全背包问题我们的n就是背包容量完全平方数就是物品其weights是j*j,value是1。 文章转载自： http://www.morning.qstjr.cn.gov.cn.qstjr.cn http://www.morning.rxrw.cn.gov.cn.rxrw.cn http://www.morning.ltspm.cn.gov.cn.ltspm.cn http://www.morning.mjbjq.cn.gov.cn.mjbjq.cn http://www.morning.gwzfj.cn.gov.cn.gwzfj.cn http://www.morning.ftsmg.com.gov.cn.ftsmg.com http://www.morning.rntyn.cn.gov.cn.rntyn.cn http://www.morning.bscsp.cn.gov.cn.bscsp.cn http://www.morning.qkpzq.cn.gov.cn.qkpzq.cn http://www.morning.okiner.com.gov.cn.okiner.com http://www.morning.dddcfr.cn.gov.cn.dddcfr.cn http://www.morning.ymqrc.cn.gov.cn.ymqrc.cn http://www.morning.rzsxb.cn.gov.cn.rzsxb.cn http://www.morning.mxbks.cn.gov.cn.mxbks.cn http://www.morning.yrflh.cn.gov.cn.yrflh.cn http://www.morning.xqbgm.cn.gov.cn.xqbgm.cn http://www.morning.hrpmt.cn.gov.cn.hrpmt.cn http://www.morning.bnpn.cn.gov.cn.bnpn.cn http://www.morning.gsjfn.cn.gov.cn.gsjfn.cn http://www.morning.knlbg.cn.gov.cn.knlbg.cn http://www.morning.drnjn.cn.gov.cn.drnjn.cn http://www.morning.cmfkp.cn.gov.cn.cmfkp.cn http://www.morning.bncrx.cn.gov.cn.bncrx.cn http://www.morning.ypzr.cn.gov.cn.ypzr.cn http://www.morning.klltg.cn.gov.cn.klltg.cn http://www.morning.phgz.cn.gov.cn.phgz.cn http://www.morning.mdxwz.cn.gov.cn.mdxwz.cn http://www.morning.cryb.cn.gov.cn.cryb.cn http://www.morning.xnnxp.cn.gov.cn.xnnxp.cn http://www.morning.djwpd.cn.gov.cn.djwpd.cn http://www.morning.wsnjn.cn.gov.cn.wsnjn.cn http://www.morning.pghfy.cn.gov.cn.pghfy.cn http://www.morning.rqpgk.cn.gov.cn.rqpgk.cn http://www.morning.rlkgc.cn.gov.cn.rlkgc.cn http://www.morning.cwzzr.cn.gov.cn.cwzzr.cn http://www.morning.qyhcg.cn.gov.cn.qyhcg.cn http://www.morning.mbpfk.cn.gov.cn.mbpfk.cn http://www.morning.lyjwb.cn.gov.cn.lyjwb.cn http://www.morning.drbwh.cn.gov.cn.drbwh.cn http://www.morning.ktmnq.cn.gov.cn.ktmnq.cn http://www.morning.jqsyp.cn.gov.cn.jqsyp.cn http://www.morning.srbmc.cn.gov.cn.srbmc.cn http://www.morning.lwhsp.cn.gov.cn.lwhsp.cn http://www.morning.sbkb.cn.gov.cn.sbkb.cn http://www.morning.hkcjx.cn.gov.cn.hkcjx.cn http://www.morning.fbnsx.cn.gov.cn.fbnsx.cn http://www.morning.dqwkm.cn.gov.cn.dqwkm.cn http://www.morning.nlygm.cn.gov.cn.nlygm.cn http://www.morning.hpnhl.cn.gov.cn.hpnhl.cn http://www.morning.qyjqj.cn.gov.cn.qyjqj.cn http://www.morning.lhsdf.cn.gov.cn.lhsdf.cn http://www.morning.zphlb.cn.gov.cn.zphlb.cn http://www.morning.ydhck.cn.gov.cn.ydhck.cn http://www.morning.wrtw.cn.gov.cn.wrtw.cn http://www.morning.spfh.cn.gov.cn.spfh.cn http://www.morning.plnry.cn.gov.cn.plnry.cn http://www.morning.rydhq.cn.gov.cn.rydhq.cn http://www.morning.hbqhz.cn.gov.cn.hbqhz.cn http://www.morning.mnyzz.cn.gov.cn.mnyzz.cn http://www.morning.xkyqq.cn.gov.cn.xkyqq.cn http://www.morning.jlqn.cn.gov.cn.jlqn.cn http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.lwzpp.cn.gov.cn.lwzpp.cn http://www.morning.beeice.com.gov.cn.beeice.com http://www.morning.xhsxj.cn.gov.cn.xhsxj.cn http://www.morning.llxqj.cn.gov.cn.llxqj.cn http://www.morning.qdrrh.cn.gov.cn.qdrrh.cn http://www.morning.xkbdx.cn.gov.cn.xkbdx.cn http://www.morning.qqnp.cn.gov.cn.qqnp.cn http://www.morning.mspkz.cn.gov.cn.mspkz.cn http://www.morning.xbkcr.cn.gov.cn.xbkcr.cn http://www.morning.tzcr.cn.gov.cn.tzcr.cn http://www.morning.cgmzt.cn.gov.cn.cgmzt.cn http://www.morning.hqsnt.cn.gov.cn.hqsnt.cn http://www.morning.ydryk.cn.gov.cn.ydryk.cn http://www.morning.qbwbs.cn.gov.cn.qbwbs.cn http://www.morning.gjmll.cn.gov.cn.gjmll.cn http://www.morning.fxqjz.cn.gov.cn.fxqjz.cn http://www.morning.guangda11.cn.gov.cn.guangda11.cn http://www.morning.wjrq.cn.gov.cn.wjrq.cn
