做请柬的网站,开发一款像淘宝的app需要多少钱,自己开网站工作室,邦策网站建设系列文章目录
代码随想录——回溯 代码随想录——贪心算法 代码随想录——动态规划 文章目录 系列文章目录概述简单斐波那契数***爬楼梯***使用最小花费爬楼梯不同路径不同路径 II***整数拆分***不同的二叉搜索树***普通0-1背包***分割等和子集***最后一块石头的重量 II***目标…系列文章目录
代码随想录——回溯 代码随想录——贪心算法 代码随想录——动态规划 文章目录 系列文章目录概述简单斐波那契数***爬楼梯***使用最小花费爬楼梯不同路径不同路径 II***整数拆分***不同的二叉搜索树***普通0-1背包***分割等和子集***最后一块石头的重量 II***目标和***一和零零钱兑换 II***组合总和 Ⅳ爬楼梯进阶版***零钱兑换完全平方数单词拆分 概述 简单
斐波那契数
链接https://leetcode.cn/problems/fibonacci-number/description/ 优化点在于只需要维护两个数不知道为什么用vector比用数组快
***爬楼梯
链接https://leetcode.cn/problems/climbing-stairs/description/ 这题展示了动态规划的核心思想就是找到当前值和之前值的关系不一定是前一个也有可能是前几个。这里可以选择上两层或者上一层那么到达第n层的方法就是到达第n-1层的方法加上到达第n-2层的方法其实就是变相的斐波那契数。
***使用最小花费爬楼梯
链接https://leetcode.cn/problems/min-cost-climbing-stairs/description/ 题目描述的很不清晰这个花费是指从当前台阶继续往上走需要付的钱而到楼顶是指从跨过最后一个台阶所以最后或者倒数第二个台阶的花费也要加上。思路就是计算到达每一个台阶的最小花费n的最小花费 到达n-1的最小花费 n-1本身需要的花费或者到达n-2的最小花费 n-2本身需要的花费。从而形成动态规划。
不同路径
链接https://leetcode.cn/problems/unique-paths/description/ 到每个格子的路径等于左边和上面格子路径数之和注意处理边界。用vector比用数组快很多
不同路径 II
https://leetcode.cn/problems/unique-paths-ii/description/ 上一题的变种相加之前判断一下是否有障碍有障碍的不加。
***整数拆分
https://leetcode.cn/problems/integer-break/description/ 动态规划的思路不好想。一个数拆分乘积有两种方式例如7可以拆分成25这种就是只拆分成两个数也可以拆分成223即把后面的5又拆分成23.第一种方式是可以直接计算的第二种方式的5就是迭代的关键那只要找到5的最大拆分乘积那么总的乘积就是最大的。以此类推将初始值的dp[0] dp[1] 0。
***不同的二叉搜索树
https://leetcode.cn/problems/unique-binary-search-trees/description/ 对于n如果1做头结点那么左子结点有0个数右子结点有n - 1个数那么1做头结点就有dp[0] * dp[n - 1]种情况以此类推相加到n。初始化dp[0] dp[1] 1。
***普通0-1背包
https://kamacoder.com/problempage.php?pid1046 有点类似于不同路径要转变为二维数组来做。i是物体编号j是背包空间dp[i][j]的含义为j空间的情况下前i个物体任意拿的最大价值。dp[i][j]迭代过程为如果不拿第i个物体则dp[i][j] dp[i - 1][j],如果拿则dp[i][j] dp[i - 1][j - space[i]],意思是空间满足拿i的情况下前i - 1个物体任意拿的最大值。取两种情况的最大值为dp[i][j]。 用一维数组也可以做。因为迭代每次都只使用上一层的数组所以只需要一个一维数组不断更新但这样带来一个问题如果是从小到大去遍历背包大小那么新得到的本层数据就会覆盖上层数据所以应该从大到小去遍历。
***分割等和子集
https://leetcode.cn/problems/partition-equal-subset-sum/description/ 先求出总和的一半如果是奇数就直接返回false。回溯会超时数组相当于重量和价值相等所以在n重量下最大的价值就是n所以求相等就是求最大然后套动态规划模板。
***最后一块石头的重量 II
https://leetcode.cn/problems/last-stone-weight-ii/description/ 本质上就是将石头分为两堆两者之差尽可能小所以将target/2选的石头尽可能接近这个值就满足条件。要把这些问题转化为背包问题
***目标和
https://leetcode.cn/problems/target-sum/description/ 分成正负两堆正负total正-负tartget所以正(totaltartget)/2,这时候就转化为了有多少种方法可以组成正与在范围内求最大值不同求多少种方法等于 选不选 的方法总和。本层此位置等于上一层的此位置dp[j - nums[j] ] 的位置
***一和零
https://leetcode.cn/problems/ones-and-zeroes/description/ 这道题的target是二维的所以曾经的一维数组现在要变成二维而且最重要的是dp[i][j]也要两个维度同时减 类似于dp[j][k] max(dp[j][k],dp[j - zero][k - one] 1);。
零钱兑换 II
https://leetcode.cn/problems/coin-change-ii/description/ 完全背包意味着每个选项可以多选那么要从头开始遍历。又是有多少种选择所以将结果相加。
***组合总和 Ⅳ
https://leetcode.cn/problems/combination-sum-iv/description/ 如果是排序则不同的顺序算作不同的结果这时候应该外层循环背包内层循环物品。此外
dp[j - nums[i]] INT_MAX - dp[j] 和 dp[j - nums[i]] dp[j] INT_MAX 是不同的 因为当两个数都很大时用加法直接就溢出了用减法能保证不溢出所以应该用第一种。
爬楼梯进阶版
https://kamacoder.com/problempage.php?pid1067 可以重复拿求顺序。
***零钱兑换
https://leetcode.cn/problems/coin-change/description/ 取最小值意味着dp[i]满足条件的最小值递推公式就是dp[i] min(dp[i],dp[i - coins[j]] 1);选意味着1不选意味着还用上一层的最小值。
完全平方数
https://leetcode.cn/problems/perfect-squares/description/ 和上一题基本上一样。
单词拆分
还没写
