网站 提示建设中,移动选号码网上选号手机号,北京网站如何制作,贵阳企业自助建站废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【动态规划】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【动态规划】使用【数组】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。明确目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
零钱兑换【MID】
通过这道题推导下动态规划状态转移方程的推导思路
题干 回溯的思路就是无重复可复选的组合树解法
解题思路
先分析明确 这个问题可以用动态规划解决
问题分析
首先这个问题是动态规划问题因为它具有「最优子结构」的。要符合「最优子结构」子问题间必须互相独立【无后效性】。 什么是相互独立比如说假设你考试每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩那么你的子问题就是要把语文考到最高数学考到最高…… 为了每门课考到最高你要把每门课相应的选择题分数拿到最高填空题分数拿到最高…… 当然最终就是你每门课都是满分这就是最高的总成绩。得到了正确的结果最高的总成绩就是总分。因为这个过程符合最优子结构「每门科目考到最高」这些子问题是互相独立互不干扰的。但是如果加一个条件你的语文成绩和数学成绩会互相制约不能同时达到满分数学分数高语文分数就会降低反之亦然。这样的话显然你能考到的最高总成绩就达不到总分了按刚才那个思路就会得到错误的结果。因为「每门科目考到最高」的子问题并不独立语文数学成绩户互相影响无法同时最优所以最优子结构被破坏。 回到凑零钱问题为什么说它符合最优子结构呢假设你有面值为 1, 2, 5 的硬币你想求 amount 11 时的最少硬币数原问题如果你知道凑出 amount 10, 9, 6 的最少硬币数子问题你只需要把子问题的答案加一再选一枚面值为 1, 2, 5 的硬币求个最小值就是原问题的答案。因为硬币的数量是没有限制的所以子问题之间没有相互制约是互相独立的
如何列出状态转移方程
那么既然知道了这是个动态规划问题就要思考如何列出正确的状态转移方程
确定 base case这个很简单显然目标金额 amount 为 0 时算法返回 0因为不需要任何硬币就已经凑出目标金额了。确定「状态」也就是原问题和子问题中会变化的变量。由于硬币数量无限硬币的面额也是题目给定的只有目标金额会不断地向 base case 靠近所以唯一的「状态」就是目标金额 amount。确定「选择」也就是导致「状态」产生变化的行为。目标金额为什么变化呢因为你在选择硬币你每选择一枚硬币就相当于减少了目标金额。所以说所有硬币的面值就是你的「选择」。明确 dp 函数/数组的定义。我们采用动态规划自底向上求解所以dp 数组的定义当目标金额为 i 时至少需要 dp[i] 枚硬币例如目标金额为11时至少需要dp[11]种硬币组合
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法动态规划 技巧无 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 最少货币数* param arr int整型一维数组 the array* param aim int整型 the target* return int整型*/public int coinChange(int[] coins, int amount) {// 0 异常情况if (coins.length 0 || amount 0) {return -1;}// 1 定义动态规划数组dp[i] 表示组成目标金额i【状态】的最少货币数量【选择】int[] dp new int[amount 1];// 所有数值初始化为目标金额初始化目标金额最多有amount种组合当货币为1时Arrays.fill(dp, amount1);// 2 定义base case :目标金额为0 需要的货币数量为0dp[0] 0;// 3 列举所有状态求每种状态的最少货币选择for (int i 1; i dp.length; i) {// 内层 for 循环在求所有选择的最小值for (int coin : coins) {// 剪枝如果目标金额小于coin则没有任何选择子问题无解if (i coin) {continue;}// 状态转移方程目标金额的货币组合数1当前货币占用1个组合位置dp[i-coin](差额前值的最少组合数)dp[i] Math.min(dp[i], dp[i - coin] 1);}}// 如果金额为10的选择大于10种例如11种那会出现不足1元的币种显然不满足条件return dp[amount] amount? -1: dp[amount];}
}为啥 dp 数组中的值都初始化为 amount 1 呢因为凑成 amount 金额的硬币数最多只可能等于 amount全用 1 元面值的硬币所以初始化为 amount 1 就相当于初始化为正无穷便于后续取最小值如果没有取到最小值没有更改初始化的值则认为没有找到最少的组合方式
为啥不直接初始化为 int 型的最大值 Integer.MAX_VALUE 呢因为后面有 dp[i - coin] 1这就会导致整型溢出
复杂度分析
时间复杂度O(S*n)其中 S 是金额n 是面额数。我们一共需要计算 O(S)个状态S 为题目所给的总金额。对于每个状态每次需要枚举 n 个面额来转移状态所以一共需要 O(S*n) 的时间复杂度。
空间复杂度O(S)。数组 dp 需要开长度为总金额 S 的空间。
爬楼梯【EASY】
再来一道动规里相对来说较为基础的题目
题干 和零钱兑换类似不过和零钱兑换不同的是要记录的是兑换的方法有多少种而不是最少数量的组合
解题思路
动态规划定义状态转移公式dp[i]dp[i-1]dp[i-2]
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法动态规划 技巧无 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param number int整型* return int整型*/public int climbStairs(int n) {// 1 特殊情况判断如果目标台阶数为0则有0种跳法if (n 1) {return 0;}// 2 定义状态转移表,dp[i]表示跳上i级台阶总共有dp[i]种跳法int[] dp new int[n 1];// 3 定义base case:因为一次只能跳1或2所以初始状态为dp[0],dp[1]dp[0] 1;dp[1] 1;// 4 进行状态转移穷举所有状态对应的跳法for (int i 2; i dp.length; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}复杂度分析
时间复杂度为ON迭代此时为N 空间复杂度为ON状态转移表的大小为N
还有一种压缩空间复杂度的写法就是用滚动数组
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param number int整型* return int整型*/public int climbStairs(int n) {// 1 特殊情况判断如果目标台阶数为0则有0种跳法if (n 0 || n 1) {return 1;}int first 1;int second 1;int result 0;// 2 数组滚动更新for (int i 2; i n; i) {result first second;first second;second result;}return result;}
}空间复杂度可以降到O1但是没有普适性。
买卖股票的最佳时机I【EASY】
来从动态规划最简单的题开始训练
题干 解题思路
按照动态规划的思路进行状态设计和状态转移方程编写
1 定义状态定义子问题
dp[i]表示第i天卖出股票的最大利润。
2 状态转移方程描述子问题之间的联系
根据状态的定义由于 prices[i] 一定会被选取并且以 prices[i] 结尾的卖出日期与以 prices[i - 1] 结尾的卖出日期只相差一个元素 nums[i] 。假设数组 prices的值全都严格大于 0那么一定有 dp[i] dp[i - 1] prices[i]-prices[i-1]。可是 dp[i - 1] 有可能是负数于是分类讨论
如果 dp[i - 1] 0那么可以把prices[i]-prices[i-1]直接接在 dp[i - 1] 表示的那个数组的后面得到和更大的利润如果 dp[i - 1] 0那么 prices[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」此时单独的利润prices[i]-prices[i-1]的值就是 dp[i]。
以上两种情况的最大值就是 dp[i] 的值
3 初始化状态
dp[0] 根据定义初始化第1天买入第一天卖出利润为0初始化利润值
4 求解方向
这里采用自底向上从最小的状态开始求解
5 找到最终解
这里的dp[i]只是第i天卖出的最大利润并不是题目中的问题买卖股票的最大利润所以最终解并不是子问题的解需要用一个MAX值承载通过与dp[i]比较更新最终解
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法动态规划 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param prices int整型一维数组* return int整型*/public int maxProfit (int[] prices) {// 1 初始化动态规划数组维护第i天卖出的最大利润int[] dp new int[prices.length];int maxValue dp[0];for (int i 1; i prices.length; i) {// 2 计算当前天和前一天卖出的利润差int curValue prices[i] - prices[i - 1];// 3 状态转移方程第i天卖出的最大利润为如果i-1天卖出的最大利润为负数则舍弃否则累加第i天的最大利润dp[i] dp[i - 1] 0 ? curValue : dp[i - 1] curValue;// 4 每次计算完最小问题后更新最大值maxValue Math.max(dp[i], maxValue);}return maxValue;}
}复杂度分析
时间复杂度遍历了一遍数组所以时间复杂度为ON 空间复杂度定义了动规数组空间复杂度为ON
打家劫舍【MID】
来一道MID的题目打家劫舍也是耳闻已久的题目了
题干 解题思路
还是用动态规划的方式解题
1 定义状态定义子问题
子问题是和原问题相似但规模较小的问题。例如这道小偷问题原问题是 “从全部房子中能偷到的最大金额”将问题的规模缩小子问题就是 “从 i个房子中能按照规则偷到的最大金额 ”
dp[i]表示能按照规则从i间房子所能偷到的最大利润。 2 状态转移方程描述子问题之间的联系 3 初始化状态
这里采用自底向上从最小的状态开始求解
当k0时没有房子所以dp[0]0;当k1时有一间房子所以只能偷这个金额为dp[1]nums[0]
5 找到最终解 代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法动态规划 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;class Solution {public int rob(int[] nums) {// 1 特殊情况处理如果不存在房间只能偷到0元if (nums.length 1) {return 0;}// 2 定义状态转移表:dp[i] 表示偷窃前i间房子中的最大金额原问题为偷窃全部房间的最大金额nums.lengthint[] dp new int[nums.length 1];// 3 初始化base case,前0间房金额为0第一间房的金额就是nums[0]dp[0] 0;dp[1] nums[0];// 4 定义状态转移方程for (int i 2; i dp.length; i) {// 前i间房子的偷窃最大金额前i-2间房子最大值第i间房子与前i-1间房子的最大值dp[i] Math.max(dp[i - 2] nums[i - 1], dp[i - 1]);}return dp[nums.length];}
}为了便于理解补充一个合nums数组下标对齐的版本
import java.util.*;class Solution {public int rob(int[] nums) {// 1 特殊情况处理如果不存在房间只能偷到0元if (nums.length 1) {return 0;}// 2 定义状态转移表:dp[i] 表示偷窃前i间房子中的最大金额原问题为偷窃全部房间的最大金额nums.length-1int[] dp new int[nums.length];// 3 初始化base case,前0间房金额为0第一间房的金额就是nums[0]if (nums.length 1) {return nums[0];}if (nums.length 2) {return Math.max(nums[1], nums[0]);}dp[0] nums[0];dp[1] Math.max(nums[1], nums[0]);// 4 定义状态转移方程for (int i 2; i dp.length; i) {// 前i间房子的偷窃最大金额前i-2间房子最大值第i间房子与前i-1间房子的最大值dp[i] Math.max(dp[i - 2] nums[i], dp[i - 1]);}return dp[nums.length - 1];}
}复杂度分析
时间复杂度遍历了一遍数组所以时间复杂度为ON 空间复杂度定义了动规数组空间复杂度为ON
拓展知识动态规划与贪心算法
动态规划
动态规划Dynamic Programming简称DP是一种解决复杂问题的算法设计技术常用于优化问题和组合问题的求解。它通过将原问题分解成子问题并保存子问题的解以避免重复计算从而提高算法的效率。动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。
动态规划的基本思想可以总结为以下几个步骤 定义问题的状态首先要明确定义问题的状态这些状态可以用来描述问题的各种情况。 找到状态转移方程状态转移方程描述了问题之间的联系即如何从一个状态转移到另一个状态。这通常涉及到问题的递归关系通过这个关系可以从较小规模的子问题得到更大规模的问题的解。 初始化状态确定初始状态的值这通常是问题规模最小的情况下的解。 自底向上或自顶向下求解动态规划可以采用自底向上Bottom-Up或自顶向下Top-Down的方式求解问题。自底向上是从最小的状态开始逐步计算直到得到最终问题的解自顶向下是从最终问题开始递归地计算子问题的解直到达到最小状态。 根据问题的要求从状态中找到最终解。
动态规划常见的应用领域包括 最长公共子序列问题在两个序列中找到一个最长的共同子序列用于比较字符串相似性。 背包问题在给定一定容量的背包和一组物品的情况下选择一些物品放入背包使得物品的总价值最大或总重量不超过背包容量。 最短路径问题求解图中两点之间的最短路径如Dijkstra算法和Floyd-Warshall算法。 硬币找零问题给定一组硬币面额和一个目标金额找到使用最少数量的硬币组合成目标金额。 斐波那契数列问题求解斐波那契数列的第n个数通过动态规划可以避免重复计算。
动态规划是一种强大的问题求解方法但它并不适用于所有类型的问题。在使用动态规划时需要仔细分析问题的性质确保问题具有重叠子问题和最优子结构性质以确保动态规划算法能够有效地解决问题。
贪心算法
贪心算法Greedy Algorithm是一种常用的问题求解策略通常用于解决最优化问题如最短路径、最小生成树、背包问题等。贪心算法的基本思想是每一步都选择当前状态下的最优解而不考虑全局的最优解希望通过局部最优的选择最终达到全局最优。贪心算法通常是一种高效的方法但并不是所有问题都适合使用贪心算法因为有些问题的最优解不一定可以通过贪心选择得到。
贪心算法的一般步骤如下 定义问题的优化目标明确问题的约束条件。 从问题的初始状态开始通过一系列选择每次选择局部最优解更新当前状态。 检查是否满足问题的约束条件和终止条件。如果不满足则回到第2步继续选择如果满足则算法结束。 对于某些问题需要证明贪心选择的局部最优解确实能够导致全局最优解这需要数学证明或者举出反例。
以下是一些常见的问题可以使用贪心算法解决 最小生成树问题如Kruskal算法和Prim算法用于寻找无向图中的最小生成树。 最短路径问题如Dijkstra算法用于寻找图中两点之间的最短路径。 背包问题如分数背包问题和0/1背包问题可以使用贪心算法进行求解。 活动选择问题如贪心选择活动安排最多的问题可以使用贪心算法求解。
需要注意的是并非所有问题都适合使用贪心算法因为有些问题的最优解可能需要全局搜索或者动态规划等其他算法。因此在应用贪心算法之前需要仔细分析问题的特点和性质以确定贪心算法是否合适。
动态规划与贪心算法区别
动态规划Dynamic Programming和贪心算法Greedy Algorithm都是常见的问题求解策略但它们在问题求解时有很大的区别适用于不同类型的问题和场景。
区别 最优子结构性质 动态规划动态规划问题通常具有最优子结构性质即全局最优解可以通过子问题的最优解来构造。动态规划通常涉及到将问题划分为重叠的子问题然后利用这些子问题的解来构建全局最优解。贪心算法贪心算法通常涉及到每一步选择当前状态下的最优解但不一定具有最优子结构性质。贪心算法通常是通过一系列局部最优选择来达到全局最优但不能保证一定能够得到全局最优解。 选择的灵活性 动态规划在动态规划中可以在每个子问题中考虑多种选择并计算每种选择的代价或价值然后选择最优的。通常需要一个状态转移方程来描述问题的子结构和递归关系。贪心算法贪心算法在每一步都选择当前状态下的最优解不考虑其他选择的影响。它通常适用于问题具有贪心选择性质的情况即通过局部最优选择能够得到全局最优解。
问题解决场景 动态规划适用场景 当问题的最优解可以通过子问题的最优解来构造时通常使用动态规划。典型问题包括 最短路径问题如Dijkstra算法最长公共子序列问题背包问题如0/1背包问题编辑距离问题 需要存储和重用子问题的解通常使用表格或数组来实现。 贪心算法适用场景 当问题具有贪心选择性质即通过每一步的局部最优选择能够达到全局最优时可以使用贪心算法。典型问题包括 最小生成树问题如Prim算法和Kruskal算法哈夫曼编码问题活动选择问题货币找零问题 贪心算法通常更简单和高效但不能解决所有问题因为它没有全局的视野。
总之动态规划和贪心算法是两种不同的问题求解策略根据问题的特性和要求选择合适的算法非常重要。有些问题可以同时使用这两种策略的思想即使用贪心算法的局部最优性来设计动态规划的状态转移方程。
