大企业网站样式,建设信用卡银行商城网站,软件工程就业岗位,品牌策划公司怎么找客户509. 斐波那契数
力扣题目链接
题目#xff1a;斐波那契数#xff08;通常用F(n)表示#xff09;形成的序列称为斐波那契数列 。该数列由0和1开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1
F(n) F(n - 1) F(n…509. 斐波那契数
力扣题目链接
题目斐波那契数通常用F(n)表示形成的序列称为斐波那契数列 。该数列由0和1开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1给定 n 请计算 F(n) 。
思路数据量不大递推一下
通过代码
class Solution {
public:int fib(int n) {if(n 2)return n;int a 0, b 1, c;for(int i 0; i n - 1; i){c a b;a b;b c;}return c;}
};70. 爬楼梯
力扣题目链接
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢
思路每一级台阶都可以由前两个台阶走到前一个台阶跨一步前两个台阶跨两步
通过代码
class Solution {
public:int climbStairs(int n) {vectorint steps(46, 0);steps[1] 1;steps[2] 2;for(int i 3; i n; i)steps[i] steps[i - 1] steps[i - 2];return steps[n];}
};
746. 使用最小花费爬楼梯
力扣题目链接
题目给你一个整数数组cost 其中cost[i] 是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为0 或下标为1的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
思路可以有两个途径得到dp[i]一个是dp[i-1]一个是dp[i-2]。dp[i-1]跳到dp[i]需要花费dp[i - 1] cost[i - 1]。dp[i-2]跳到dp[i]需要花费dp[i-2] cost[i-2]。
那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢一定是选最小的所以dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])
通过代码
class Solution {
public:int minCostClimbingStairs(vectorint cost) {int n cost.size();vectorint dp(n 1, 0);dp[0] 0;dp[1] 0;for(int i 2; i n; i)dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);return dp[n];}
};62.不同路径
力扣题目链接
题目一个机器人位于一个m x n网格的左上角起始点在下图中标记为“Start”。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径
思路每个网格只能从其上方或左边过来因此其路径数为其上方和左侧之和。
通过代码
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m, vectorint (n));for(int i 0; i n; i)dp[0][i] 1;for(int i 0; i m; i)dp[i][0] 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
力扣题目链接
题目一个机器人位于一个m x n网格的左上角起始点在下图中标记为“Start”。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径网格中的障碍物和空位置分别用 1 和 0 来表示。
思路和前一题类似只不过需要处理一下有障碍的情况。状态转移的时候有障碍的格子赋0即可初始化的时候一旦遇到障碍就要结束。
通过代码
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size(), n obstacleGrid[0].size();vectorvectorint dp(m, vectorint (n, 0));if(obstacleGrid[0][0])dp[0][0] 0;elsedp[0][0] 1;for(int i 1; i n obstacleGrid[0][i] 0; i)dp[0][i] dp[0][i - 1];for(int i 1; i m obstacleGrid[i][0] 0; i)dp[i][0] dp[i - 1][0];for(int i 1; i m; i)for(int j 1; j n; j){if(obstacleGrid[i][j])dp[i][j] 0;elsedp[i][j] dp[i -1][j] dp[i][j - 1];}return dp[m - 1][n - 1];}
};343. 整数拆分
力扣题目链接
题目给定一个正整数n将其拆分为k个正整数的和k 2并使这些整数的乘积最大化。返回你可以获得的最大乘积 。
思路dp[i]表示i的最大乘积。有两种渠道可以得到dp[i]一种是j*(i - j)另一种是dp[j] * (i - j)。前者代表不对j拆分后者代表对j进行拆分由于j差分的最大乘积在之前的遍历已经算出来了所以直接用dp[j]即可。在这种渠道选一个大的即可最后在整个遍历过程中取一个大的。
通过代码
class Solution {
public:int integerBreak(int n) {vectorint dp(n 1);dp[1] 1;dp[2] 1;for(int i 3; i n; i){dp[i] dp[i - 1];for(int j i - 2; j 1; j--)dp[i] max(dp[i], max(dp[j], j) * (i - j));}return dp[n];}
};96.不同的二叉搜索树
力扣题目链接
题目给你一个整数n求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种返回满足题意的二叉搜索树的种数。
思路dp[i]表示i个节点组成的树的种数。以j为根节点则前j-1个节点必在其左子树其种数为dp[j - 1]后i-j个节点必在其右子树其种数为dp[i - j]。所以以j为根节点的种数合计为dp[j - 1] * dp[i - j]。dp[i]的值对以1到i为根节点的种数求和即可。
通过代码
class Solution {
public:int numTrees(int n) {vectorint dp(n 1, 0);dp[0] 1;dp[1] 1;for(int i 2; i n; i)for(int j 1; j i; j)dp[i] dp[j - 1] * dp[i - j];return dp[n];}
};416. 分割等和子集
力扣题目链接
题目给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
思路首先排除一些明显无法分割的情况元素数量小于2、总和为奇数、最大元素超过总和的一半。将问题转化为01背包取一些数使得其和为target。定义dp数组dp[i][j]表示能否在下标为0到i的范围选一些数使得和为j。对于新扩展进来的数nums[i]我们有两种选择一是不选那么结果就为dp[i-1][j]二是选结果就为dp[i-1][j-nums[i]]。只要这两个结果中的一个为true那么dp[i][j]就为true。
通过代码
class Solution {
public:bool canPartition(vectorint nums) {int n nums.size(), sum 0, maxn 0;if(n 2)return false;for(int num : nums){sum num;maxn max(maxn, num);}if(sum % 2 1)return false;int target sum / 2;if(maxn target)return false;vectorbool dp(target 1, false);dp[0] true;dp[nums[0]] true;for(int i 1; i n; i)for(int j target; j nums[i]; j--)dp[j] dp[j] || dp[j - nums[i]];return dp[target];}
};1049.最后一块石头的重量II
力扣题目链接
题目有一堆石头用整数数组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 sum 0;for(int num : stones)sum num;int target sum / 2 1;vectorint dp(target, 0);for(int i 0; i stones.size(); i)for(int j target - 1; j stones[i]; j--)dp[j] max(dp[j], dp[j - stones[i]] stones[i]);return sum - dp[target - 1] - dp[target - 1];}
};494.目标和
力扣题目链接
题目给你一个非负整数数组nums和一个整数target 。向数组中的每个整数前添加或-然后串联起所有整数可以构造一个表达式
例如nums [2, 1]可以在2之前添加在1之前添加 - 然后串联起来得到表达式2-1 。
返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。
思路难在如何转化为背包问题。一旦找到转化的思路就容易了。假设加负号的整数的和为neg那么加正号的整数的和为sum-negsum为nums的总和。根据题意有(sum-neg)-negtarget即sum-2*negtarget由于sum和target都是定值因此也能求出neg为(sum-target)/2。由于是非负整数数组所以neg肯定也是非负整数不是的话就是无解。于是问题就可以转化为在nums中选一些数使得和为neg求几种选法从而转化为了01背包问题。后面不再赘述。
通过代码
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for(int num : nums)sum num;if(sum - target 0 || (sum - target) % 2)return 0;int neg (sum - target) / 2;vectorint dp(neg 1, 0);dp[0] 1;for(int i 0; i nums.size(); i)for(int j neg; j nums[i]; j--)dp[j] dp[j] dp[j - nums[i]];return dp[neg];}
};474.一和零
力扣题目链接
题目给你一个二进制字符串数组strs和两个整数m和n 。请你找出并返回 strs 的最大子集的长度该子集中最多有m个0和n个1 。
如果x的所有元素也是y的元素集合x是集合y的子集 。
思路01背包的影子很容易看出来就是背包容量有了两个维度一个是0的数量一个是1的数量。换成背包问题的表述就是背包容量为m和n求能装的字符串的最大数量。一个字符串中的1的数量和0的数量就是代价价值就是个数可以1。如果不压缩空间的话就要开三维数组因此这里仍然采用滚动数组。最外层依然是遍历字符串的个数。里面两层依次遍历背包的两个维度注意都要从后往前遍历。
通过代码
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0));for(string s : strs){int ones count(s.begin(), s.end(), 1);int zeros s.size() - ones;for(int i m; i zeros; i--)for(int j n; j ones; j--)dp[i][j] max(dp[i][j], dp[i -zeros][j - ones] 1);}return dp[m][n];}
};518.零钱兑换II
力扣题目链接
题目给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回0。
假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。
思路近乎完全背包模板题参考链接。背包容量为amount每个硬币无限数量硬币面值就是代价。注意dp[0]一定要为1。
通过代码
class Solution {
public:int change(int amount, vectorint coins) {vectorint 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];}
};377. 组合总和 Ⅳ
力扣题目链接
题目给你一个由 不同 整数组成的数组nums和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
思路完全背包。把两个for循环反过来就是排列。target背包放在外循环将nums物品放在内循环内循环从前到后遍历。
通过代码
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1, 0);dp[0] 1;for(int i 1; i target; i)for(int j 0; j nums.size(); j){if(i nums[j] dp[i] INT_MAX - dp[i - nums[j]])dp[i] dp[i - nums[j]];}return dp[target];}
};322. 零钱兑换
力扣题目链接
题目给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回-1 。你可以认为每种硬币的数量是无限的。
思路典型的完全背包。凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]。所以dp[j]要取所有dp[j - coins[i]] 1中最小的。
递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]);
注意我初始化都为-1除了dp[0]0递推的时候还要注意无解的情况。
通过代码
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, -1);dp[0] 0;for(int i 0; i coins.size(); i)for(int j coins[i]; j amount; j){if(dp[j] ! -1 dp[j - coins[i]] ! -1)dp[j] min(dp[j], dp[j - coins[i]] 1);else if(dp[j] -1 dp[j - coins[i]] ! -1)dp[j] dp[j - coins[i]] 1;} return dp[amount];}
};279.完全平方数
力扣题目链接
题目给你一个整数n返回和为n的完全平方数的最少数量 。
完全平方数是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16都是完全平方数而3和11不是。
思路n的最大值为10000所以完全平方数的范围就是1-100的平方。而且都是可以无限使用的所以就是典型的完全背包。类似于上面一道题1-100就相当于硬币面值n就相当于amount也就是背包容量。
通过代码
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for(int i 1; i 100; i)for(int j i * i; j n; j)dp[j] min(dp[j], dp[j - i * i] 1);return dp[n];}
};139.单词拆分
力扣题目链接
题目给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回 true。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
思路单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。如果确定dp[j]是true且 [j, i] 这个区间的子串出现在字典里那么dp[i]一定是truej i。
通过代码
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordSet(wordDict.begin(), wordDict.end());vectorbool dp(s.size() 1, false);dp[0] true;for(int i 1; i s.size(); i)for(int j 0; j i; j) //枚举字符串就是枚举起始位置{string word s.substr(j, i - j);if(wordSet.find(word) ! wordSet.end() dp[j])dp[i] true;}return dp[s.size()];}
};198.打家劫舍
力扣题目链接
题目你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。
思路dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。如果偷第i房间那么dp[i] dp[i - 2] nums[i]即第i-1房一定是不考虑的找出下标i-2包括i-2以内的房屋最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间那么dp[i] dp[i - 1]即考虑i-1房。
通过代码
class Solution {
public:int rob(vectorint nums) {if(nums.size() 0)return 0;if(nums.size() 1)return nums[0];vectorint dp(nums.size(), 0);dp[0] nums[0];dp[1] max(nums[0], nums[1]);for(int i 2; i nums.size(); i)dp[i] max(dp[i - 1], dp[i - 2] nums[i]);return dp[nums.size() - 1];}
};213.打家劫舍II
力扣题目链接
题目你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
思路如果偷窃了第一间房屋则不能偷窃最后一间房屋因此偷窃房屋的范围是第一间房屋到最后第二间房屋如果偷窃了最后一间房屋则不能偷窃第一间房屋因此偷窃房屋的范围是第二间房屋到最后一间房屋。所以问题就转化为了两个上一题最后取最大值即可。
通过代码
class Solution {
public:int myrob(vectorint nums, int start, int end){if(end - start 1)return nums[start];vectorint dp(nums.size(), 0);dp[start] nums[start];dp[start 1] max(nums[start], nums[start 1]);for(int i start 2; i end; i)dp[i] max(dp[i - 1], dp[i - 2] nums[i]);return dp[end - 1];}int rob(vectorint nums) {if(nums.size() 0)return 0;if(nums.size() 1)return nums[0];int res1 myrob(nums, 0, nums.size() - 1);int res2 myrob(nums, 1, nums.size());return max(res1, res2);}
};337.打家劫舍 III
力扣题目链接
题目小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为root。除了root之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫房屋将自动报警。
给定二叉树的root 。返回 在不触动警报的情况下 小偷能够盗取的最高金额。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/思路一记忆化搜索。
通过代码
class Solution {
public:unordered_mapTreeNode*, int map;int rob(TreeNode* root) {if(map.find(root) ! map.end())return map[root];if(!root)return 0;if(!root - left !root - right){map[root] root - val;return root - val;}// 偷父节点int val1 root - val;if(root - left)val1 rob(root - left - left) rob(root - left - right);if(root - right)val1 rob(root - right - left) rob(root - right - right);// 不偷父节点int val2 rob(root - left) rob(root - right);map[root] max(val1, val2);return map[root];}
};思路二树形dp。递归函数的返回值是一个长度为2的数组dp[0]表示不偷当前节点所得到的最大值dp[1]表示偷当前节点所得到的最大值。在单层递归中如果偷当前节点那么左右孩子就不能偷val1 cur-val left[0] right[0]; 。如果不偷当前节点那么左右孩子就可以偷至于到底偷不偷一定是选一个最大的所以val2 max(left[0], left[1]) max(right[0], right[1]);。最后当前节点的状态就是{val2, val1};
通过代码
class Solution {
public:vectorint robTree(TreeNode *cur){if(!cur)return {0, 0};vectorint left robTree(cur - left);vectorint right robTree(cur - right);// 偷curint val1 cur - val left[0] right[0];// 不偷curint val2 max(left[0], left[1]) max(right[0], right[1]);return {val2, val1};}int rob(TreeNode* root) {vectorint res robTree(root);return max(res[0], res[1]);}
};121. 买卖股票的最佳时机
力扣题目链接
题目给定一个数组prices它的第i个元素prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回0 。
思路一贪心。
通过代码
class Solution {
public:int maxProfit(vectorint prices) {int res INT_MIN;int low INT_MAX;for(int i 0; i prices.size(); i){low min(low, prices[i]);res max(res, prices[i] - low);}return res;}
};思路二动态规划。相邻两天的股票价格做差得到当天持有所能产生的收益beni。问题就转化为在beni中找到一段连续的时间使得收益最大。dp[i]表示持有到第i天所能产生的最大收益。对于新扩展进来的一天如果选择持有那么累计收益就为dp[i - 1] beni[i]如果选择不持有那么收益就要从当天重新计算beni[i]。二者取最大值即可。
通过代码
class Solution {
public:int maxProfit(vectorint prices) {if(prices.size() 2)return 0;vectorint beni;for(int i 1; i prices.size(); i)beni.push_back(prices[i] - prices[ i- 1]);int n beni.size(), res;vectorint dp(n, 0);dp[0] beni[0];res dp[0];for(int i 1; i n; i){dp[i] max(dp[i - 1] beni[i], beni[i]);res max(res, dp[i]);}return res 0 ? 0 : res;}
};122.买卖股票的最佳时机II
力扣题目链接
题目给你一个整数数组prices其中prices[i]表示某支股票第i天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买然后在同一天出售。返回你能获得的最大利润 。
思路在贪心一章我们用收集每天的正利润来做这里用动态规划做。dp[i][0]表示第i天不持有股票的最大收益dp[i][1]表示第i天持有股票的最大收益。对于dp[i][0]可以由前一天的两个状态推出如果前一天也没有持有股票并且今天也选择不持有股票那么收益就为dp[i-1][0]如果前一天持有了股票并且今天选择不持有即卖出收益为dp[i-1][1]prices[i]取二者较大值更新状态即可。dp[i][1]同理如果前一天没有持有股票今天选择持有股票收益为dp[i-1][0]-prices[i]购买股票需要花钱所以要减去prices[i]如果前一天持有了股票并且今天不卖出收益为dp[i-1][1]取二者较大值更新状态即可。
通过代码
class Solution {
public:int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(), vectorint(2,0));dp[0][1] -prices[0];for(int i 1; i prices.size(); 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[prices.size() - 1][0];}
};123.买卖股票的最佳时机III
力扣题目链接
题目给定一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
思路一天一共就有五个状态
没有操作 其实我们也可以不设置这个状态第一次持有股票第一次不持有股票第二次持有股票第二次不持有股票
dp[i][j]中 i表示第i天j为 [0 - 4] 五个状态dp[i][j]表示第i天状态j所剩最大现金。注意状态j表示第i天仍然处于这个状态。
达到dp[i][1]状态有两个具体操作
操作一第i天买入股票了那么dp[i][1] dp[i-1][0] - prices[i]操作二第i天没有操作而是沿用前一天买入的状态即dp[i][1] dp[i - 1][1]
二者取较大值就是dp[i][1]更新后的状态。剩下的同理。
通过代码
class Solution {
public:int maxProfit(vectorint prices) {vectorvectorint dp(prices.size(), vectorint (5, 0));dp[0][1] -prices[0];dp[0][3] -prices[0];for(int i 1; i prices.size(); i){dp[i][0] dp[i - 1][0];dp[i][1] max(dp[i - 1][0] - prices[i], dp[i - 1][1]);dp[i][2] max(dp[i - 1][1] prices[i], dp[i - 1][2]);dp[i][3] max(dp[i - 1][2] - prices[i], dp[i - 1][3]);dp[i][4] max(dp[i - 1][3] prices[i], dp[i - 1][4]);}return dp[prices.size() - 1][4];}
};188.买卖股票的最佳时机IV
力扣题目链接
题目给你一个整数数组prices和一个整数k 其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。也就是说你最多可以买k次卖k次。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
思路类似于上一题只不过进行了推广可以买卖k次。接着上一题的状态往下排第三次持有股票第三次不持有股票……可以发现奇数下标都是持有股票偶数下标都是不持有股票而且状态更新也只用到上一层相同位置和其左边一个位置。用一个循环完成这个重复操作即可。
通过代码
class Solution {
public:int maxProfit(int k, vectorint prices) {vectorint dp(2 * k 1, 0);for(int i 1; i 2 * k 1; i 2)dp[i] -prices[0];for(int i 1; i prices.size(); i)for(int j 1; j 2 * k 1; j){if(j % 2 1)dp[j] max(dp[j], dp[j - 1] - prices[i]);elsedp[j] max(dp[j], dp[j - 1] prices[i]);}return dp[2 * k];}
};309.最佳买卖股票时机含冷冻期
力扣题目链接
题目给定一个整数数组prices其中第 prices[i]表示第i天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:
卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
思路首先划分状态。0持有股票可能是今天买的也可能是之前买的1不持有股票并且是两天前就卖出的冷冻期已过2今天刚卖出股票3昨天卖的股票今天是冷冻期。
要想得到状态0可能昨天就持有了股票即dp[i-1][0]也可能昨天冷冻期已过今天选择买入即dp[i-1][1] - prices[i]也可能昨天是冷冻期今天买入即dp[i-1][3] - prices[i]三者取最大值更新即可。要想得到状态1可能昨天就是状态1即dp[i-1][1]也可能昨天是冷冻期即dp[i-1][3]二者取最大值即可。要想得到状态2只可能昨天持有股票即dp[i-1][0]prices[i]要想得到状态3只可能昨天刚卖出股票即dp[i-1][2]。
通过代码
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(n, vectorint (4, 0));dp[0][0] -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][3] - prices[i]});dp[i][1] max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] dp[i - 1][0] prices[i];dp[i][3] dp[i - 1][2];}return max({dp[n - 1][1], dp[n - 1][2], dp[n - 1][3]});}
};714.买卖股票的最佳时机含手续费
力扣题目链接
题目给定一个整数数组prices其中prices[i]表示第i天的股票价格 整数fee代表了交易股票的手续费用。你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。
注意这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。
思路类似于买卖股票的最佳时机II只不过多了一个手续费在卖出的时候减去手续费即可。
通过代码
class Solution {
public:int maxProfit(vectorint prices, int fee) {vectorint dp(2, 0);dp[1] -prices[0];for(int i 1; i prices.size(); i){dp[0] max(dp[0], dp[1] prices[i] - fee);dp[1] max(dp[1], dp[0] - prices[i]);}return dp[0];}
};300.最长递增子序列
力扣题目链接
题目给你一个整数数组nums找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
思路dp[i]表示以nums[i]结尾的最长子序列长度。位置i的最长递增子序列等于j从0到i-1各个位置的最长升序子序列1的最大值。
通过代码
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint dp(nums.size(), 1);int res 1;for(int i 1; i nums.size(); i){for(int j 0; j i; j)if(nums[i] nums[j])dp[i] max(dp[i], dp[j] 1);res max(res, dp[i]);}return res;}
};674. 最长连续递增序列
力扣题目链接
题目给定一个未经排序的整数数组找到最长且连续递增的子序列并返回该序列的长度。
连续递增的子序列可以由两个下标l和rl r确定如果对于每个l i r都有nums[i] nums[i 1]那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]]就是连续递增子序列。
思路dp[i]以下标i为结尾的连续递增的子序列长度为dp[i]。如果nums[i] nums[i - 1]那么以i为结尾的连续递增的子序列长度一定等于以i - 1为结尾的连续递增的子序列长度 1 。
通过代码
class Solution {
public:int findLengthOfLCIS(vectorint nums) {vectorint dp(nums.size(), 1);int res 1;for(int i 1; i nums.size(); i){if(nums[i] nums[i - 1])dp[i] dp[i - 1] 1;res max(res, dp[i]);}return res;}
};718. 最长重复子数组
力扣题目链接
题目给两个整数数组nums1和nums2返回两个数组中公共的 、长度最长的子数组的长度 。
思路dp[i][j]表示以数组1中第i个数结尾即nums1[i-1]、数组2中第j个数结尾即nums2[j-1]的最长公共子数组的长度。如果nums1[i-1]和nums2[j-1]相同当前的最长公共子数组的长度就要更新为dp[i-1][j-1]1。之所以如此定义dp数组是为了减少初始化的麻烦。如果从下标0开始算第0行和第0列就要单独初始化。
通过代码
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {int len1 nums1.size(), len2 nums2.size();if(len1 0 || len2 0)return 0;vectorvectorint dp(len1 1, vectorint (len2 1, 0));int res 0;for(int i 1; i len1; i)for(int j 1; j len2; j){if(nums1[i - 1] nums2[j - 1])dp[i][j] dp[i - 1][j - 1] 1;res max(res, dp[i][j]);}return res;}
};1143.最长公共子序列
力扣题目链接
题目给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 返回0 。
一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace是abcde的子序列但aec不是abcde的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
思路类似上一题只不过上一题要求连续这一题可以不连续。dp[i][j]表示长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列长度。之所以如此设置还是为了避免初始化的麻烦。如果text1[i - 1] 与 text2[j - 1]相同那么找到了一个公共元素所以dp[i][j] dp[i - 1][j - 1] 1;
如果text1[i - 1] 与 text2[j - 1]不相同那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列取最大的。
通过代码
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int len1 text1.size(), len2 text2.size();vectorvectorint dp(len1 1, vectorint (len2 1, 0));for(int i 1; i len1; i)for(int j 1; j len2; j){if(text1[i - 1] text2[j - 1])dp[i][j] dp[i - 1][j - 1] 1;elsedp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}return dp[len1][len2];}
};1035.不相交的线
力扣题目链接
题目在两条独立的水平线上按给定的顺序写下nums1和nums2中的整数。现在可以绘制一些连接两个数字nums1[i]和nums2[j]的直线这些直线需要同时满足
nums1[i] nums2[j]且绘制的直线不与任何其他连线非水平线相交。
请注意连线即使在端点也不能相交每个数字只能属于一条连线。
以这种方法绘制线条并返回可以绘制的最大连线数。
思路只有相同的数字才能连线不就是公共子序列吗。不允许线相交就是子序列得按顺序来。所以本题和上一题最长公共子序列是一样的代码都只要改个数组名。
通过代码
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {int len1 nums1.size(), len2 nums2.size();vectorvectorint dp(len1 1, vectorint (len2 1, 0));for(int i 1; i len1; i)for(int j 1; j len2; j){if(nums1[i - 1] nums2[j - 1])dp[i][j] dp[i - 1][j - 1] 1;elsedp[i][j] max(dp[i][j - 1], dp[i - 1][j]);}return dp[len1][len2];}
};53. 最大子序和
力扣题目链接
题目给你一个整数数组nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。
思路上次使用贪心做的这回用动规。dp[i]表示包括下标i以nums[i]为结尾的最大连续子序列和为dp[i]。对于nums[i]可以选择接在前一个序列后面则和为dp[i-1]nums[i]也可以选择自己单开一个序列则和为nums[i]选一个大的更新即可。
通过代码
class Solution {
public:int maxSubArray(vectorint nums) {vectorint dp(nums.size(), 0);dp[0] nums[0];int res dp[0];for(int i 1; i nums.size(); i){dp[i] max(nums[i], dp[i - 1] nums[i]);res max(res, dp[i]);}return res;}
};392.判断子序列
力扣题目链接
题目给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
思路一很容易想到通过双指针遍历两个串即可。
通过代码
class Solution {
public:bool isSubsequence(string s, string t) {int i 0, j 0;while(i s.size() j t.size()){if(s[i] t[j])i;j;}return i s.size();}
};思路二动态规划。dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。如果s[i-1]和t[j-1]相等相同子序列长度自然要在dp[i-1][j-1]的基础上加1。如果不相等就相当于t[j-1]没出现过结果还是和dp[i][j-1]一样。
通过代码
class Solution {
public:bool isSubsequence(string s, string t) {int len1 s.size(), len2 t.size();vectorvectorint dp(len1 1, vectorint (len2 1, 0));for(int i 1; i len1; i)for(int j 1; j len2; j){if(s[i - 1] t[j - 1])dp[i][j] dp[i - 1][j - 1] 1;elsedp[i][j] dp[i][j - 1];}return dp[len1][len2] len1;}
};115.不同的子序列
力扣题目链接
题目给你两个字符串s和t统计并返回在s的子序列中t出现的个数结果需要对$ 10^97 $取模。
思路dp[i][j]表示以j为结尾的s子序列中出现以i为结尾的t的个数为dp[i][j]。当s[i]与t[j]相等时dp[i][j]可以有两部分组成。一部分是用s[j]来匹配那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母所以只需要dp[i-1][j-1]。另一部分是不用s[j]来匹配个数为dp[i][j - 1]两部分相加即为总个数。当s[j]与t[i]不相等时dp[i][j]肯定无法用s[j]来匹配个数即为dp[i][j-1]。初始化比较特殊需要考虑t[0]在s中的子序列个数。
通过代码
class Solution {
public:int numDistinct(string s, string t) {const int mod 1e9 7;int len1 s.size(), len2 t.size();vectorvectorint dp(len2, vectorint (len1, 0));if(s[0] t[0])dp[0][0] 1;for(int i 1; i len1; i)if(t[0] s[i])dp[0][i] dp[0][i - 1] 1;elsedp[0][i] dp[0][i - 1];for(int i 1; i len2; i)for(int j 1; j len1; j){if(t[i] s[j])dp[i][j] (dp[i][j - 1] dp[i - 1][j - 1]) % mod;elsedp[i][j] dp[i][j - 1];}return dp[len2 - 1][len1 - 1];}
};583. 两个字符串的删除操作
力扣题目链接
题目给定两个单词word1和word2返回使得word1和word2相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。
思路删完之后剩的不就是最长公共子序列吗。所以这道题和最长公共子序列一样的求出最长公共子序列的长度之后用两个单词的长度和减去最长公共子序列的长度就好了。
通过代码
class Solution {
public:int minDistance(string word1, string word2) {int len1 word1.size(), len2 word2.size();vectorvectorint dp(len1 1, vectorint (len2 1, 0));for(int i 1; i len1; i)for(int j 1; j len2; j){if(word1[i - 1] word2[j - 1])dp[i][j] dp[i - 1][j - 1] 1;elsedp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}return len1 len2 - 2 * dp[len1][len2];}
};72. 编辑距离
力扣题目链接
题目给你两个单词word1和word2 请返回将word1转换成word2所使用的最少操作数 。你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
思路dp[i][j]表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最少编辑次数为dp[i][j]。如果正在比较的两个字母相等说明不用任何操作最少编辑次数还是前一次的次数dp[i-1][j-1]。如果不相等此时就有三种操作了插入、删除和替换。
首先插入和删除操作需要的次数是一样的。例如单词ad和单词a可以删除第一个单词的d也可以在第二个单词末尾添加一个d所需次数都是1。因此只需要考虑删除操作即可。删除可以删word1[i-1]也可以删word2[j-1]对应的次数分别为dp[i-1][j]1和dp[i][j-1]1。
对于替换操作替换完成之后当前比较的两个字母都是一样的了。就类似于正在比较的两个字母相等的情况次数为dp[i-1][j-1]1。
上述三者取最小的更新状态即可。初始化时由于一个单词长度为0所以另一个单词只能删除全部字母因此初始化为另一个单词的字母数即可。
通过代码
class Solution {
public:int minDistance(string word1, string word2) {int len1 word1.size(), len2 word2.size();vectorvectorint dp(len1 1, vectorint (len2 1, 0));for(int i 0; i len1; i)dp[i][0] i;for(int i 0; i len2; i)dp[0][i] i;for(int i 1; i len1; i)for(int j 1; j len2; j){if(word1[i - 1] word2[j - 1])dp[i][j] dp[i - 1][j - 1];elsedp[i][j] min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) 1;}return dp[len1][len2];}
};647. 回文子串
力扣题目链接
题目给你一个字符串s请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。
思路一动态规划。dp[i][j]表示区间[i,j]的子串是否是回文子串。
如果字符s[i]和s[j]不同区间[i,j]肯定不是回文串dp[i][j]为false如果字符s[i]和s[j]相同 如果i和j相同即整个区间只有一个字符那区间[i,j]还是回文串dp[i][j]为true如果i和j相差1相邻即整个区间只有两个字符那区间[i,j]还是回文串dp[i][j]为true如果i和j不相邻区间[i1, j-1]是回文串那整个就是回文串即dp[i][j]取决于dp[i1][j-1]。
通过代码
class Solution {
public:int countSubstrings(string s) {int res 0;int n s.size();vectorvectorbool dp(n, vectorbool (n, false));for(int i n - 1; i 0; i--)for(int j i; j n; j){if(s[i] s[j]){if(j - i 1) // 情况一和情况二{dp[i][j] true;res;}else if(dp[i 1][j - 1]){dp[i][j] true;res;}}}return res;}
};思路二双指针。判断回文子串可以从中心向两边扩散判断依次枚举中心即可注意中心可能有一个字符也可能是两个字符。
通过代码
class Solution {
public:int extend(string s, int i, int j){int res 0;while(i 0 j s.size() s[i] s[j]){i--;j;res;}return res;}int countSubstrings(string s) {int res 0;for(int i 0; i s.size(); i){res extend(s, i, i); // 以i为中心向两边扩散res extend(s, i, i 1); // 以i和i1为中心向两边扩散}return res;}
};516.最长回文子序列
力扣题目链接
题目给你一个字符串s找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
思路dp[i][j]表示区间[i,j]范围内最长回文子序列的长度。如果s[i]s[j]在s[i1, j-1]两边加上相同的字符s[i]和s[j]就能得到新的回文子序列因此dp[i][j]dp[i1][j-1]2如果s[i]!s[j]则要考虑单独加入哪个字母能够使得长度更大即dp[i][j]max(dp[i][j-1], dp[i1][j])。
注意i和j相同的时候需要手动初始化长度为1。
通过代码
class Solution {
public:int longestPalindromeSubseq(string s) {int n s.size();vectorvectorint dp(n, vectorint (n, 0));for(int i 0; i n; i)dp[i][i] 1;for(int i n - 1; i 0; i--)for(int j i 1; j n; j){if(s[i] s[j])dp[i][j] dp[i 1][j - 1] 2;elsedp[i][j] max(dp[i][j - 1], dp[i 1][j]);}return dp[0][n - 1];}
};
