分治算法,动态规划算法和贪心算法的区别和联系(一)分治算法分治算法为什么叫分治算法?分治这个名字可以分成两部:第一部分是分,表示把一个原问题分解成很多个小问题,逐个解决;第二部分是治,表示把得到的子问题的解再合起来,得到原问题的解.我们以归并排序为例子,来解释分治算法.我们要对一整个数组排序,我们不妨可以对数组的左半边排序,再对右半边排序,对于左右半边的数组来说,我们仍然对其分成左右两半排序,以此类推,最后分的不能再分的时候,我们对最终得到的子问题进行解决,再把子问题的解一层一层地合并,最后得到完整的数组.下面是归并排序算法的代码:#include#includeusingnamespaces
分治算法,动态规划算法和贪心算法的区别和联系(一)分治算法分治算法为什么叫分治算法?分治这个名字可以分成两部:第一部分是分,表示把一个原问题分解成很多个小问题,逐个解决;第二部分是治,表示把得到的子问题的解再合起来,得到原问题的解.我们以归并排序为例子,来解释分治算法.我们要对一整个数组排序,我们不妨可以对数组的左半边排序,再对右半边排序,对于左右半边的数组来说,我们仍然对其分成左右两半排序,以此类推,最后分的不能再分的时候,我们对最终得到的子问题进行解决,再把子问题的解一层一层地合并,最后得到完整的数组.下面是归并排序算法的代码:#include#includeusingnamespaces
贪心2|122.买卖股票的最佳时机II|55.跳跃游戏|45.跳跃游戏II一、122.买卖股票的最佳时机II题目链接：122.买卖股票的最佳时机II-力扣（LeetCode）需要理解最终利润是可以分解的，假如第0天买入，第3天卖出，那么利润为：prices[3]-prices[0]。相当于(prices[3]-prices[2])+(prices[2]-prices[1])+(prices[1]-prices[0])。将最终利润分解为每天利润之和，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。局部最优：收集每天的正利润，全局最优：求得最大利润。局部最优可以推出
贪心2|122.买卖股票的最佳时机II|55.跳跃游戏|45.跳跃游戏II一、122.买卖股票的最佳时机II题目链接：122.买卖股票的最佳时机II-力扣（LeetCode）需要理解最终利润是可以分解的，假如第0天买入，第3天卖出，那么利润为：prices[3]-prices[0]。相当于(prices[3]-prices[2])+(prices[2]-prices[1])+(prices[1]-prices[0])。将最终利润分解为每天利润之和，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。局部最优：收集每天的正利润，全局最优：求得最大利润。局部最优可以推出
POJ2227TheWeddingJuicer（三维接雨水BFS贪心）题意： 给出一个二维地图，其各点上权值为其高度。如果向其中填水，请问在这张地图中可以积得多少水。 地图长宽为300,高度最高为1e9。999 919 989以此图为例，可积水7 思路： 通过观察所给样例，可以发现，整个地图的储水量取决于最外围的最矮的点。若这个最矮的点被其周围比其高的点挡住，那边界就从这个最矮的点变成了其周围最矮的点。若最矮的点周围还有更矮的点，那他可以积的水为这两点的差值，同样更新一下边界。 那么我们程序化这个过程，将最外一圈放入小根堆中，然后BFS扩展，根据两种情况
题目：给你一棵树，每次操作你可以删去一条边，最少需要多少次操作使每个节点的度数都\(分析：我们可以想一想如何贪心，对于本题，最优的结果是让任意一个点连的边最多越好（但不能超过K，所以从树的底部到根，能删就删。这样可以保证，删的边数是最少的。实现：用dfs跑，注意的是如果没有父节点，tot[u]的初始化为0，其余都是有一个父节点提供一条边。对于一个节点，能删就删。#includeusingnamespacestd;#definerep(i,a,n)for(inti=a;iPII;constintinf=0x3f3f3f3f;voidread(int&x){ints=0,f=1;charch
POJ2227TheWeddingJuicer（三维接雨水BFS贪心）题意： 给出一个二维地图，其各点上权值为其高度。如果向其中填水，请问在这张地图中可以积得多少水。 地图长宽为300,高度最高为1e9。999 919 989以此图为例，可积水7 思路： 通过观察所给样例，可以发现，整个地图的储水量取决于最外围的最矮的点。若这个最矮的点被其周围比其高的点挡住，那边界就从这个最矮的点变成了其周围最矮的点。若最矮的点周围还有更矮的点，那他可以积的水为这两点的差值，同样更新一下边界。 那么我们程序化这个过程，将最外一圈放入小根堆中，然后BFS扩展，根据两种情况
题目：给你一棵树，每次操作你可以删去一条边，最少需要多少次操作使每个节点的度数都\(分析：我们可以想一想如何贪心，对于本题，最优的结果是让任意一个点连的边最多越好（但不能超过K，所以从树的底部到根，能删就删。这样可以保证，删的边数是最少的。实现：用dfs跑，注意的是如果没有父节点，tot[u]的初始化为0，其余都是有一个父节点提供一条边。对于一个节点，能删就删。#includeusingnamespacestd;#definerep(i,a,n)for(inti=a;iPII;constintinf=0x3f3f3f3f;voidread(int&x){ints=0,f=1;charch
本题为12月16日力扣每日一题题目来源:力扣第1785题题目tag:贪心题面题目描述给你一个整数数组nums，和两个整数limit与goal。数组nums有一条重要属性：abs(nums[i])返回使数组元素总和等于goal所需要向数组中添加的最少元素数量，添加元素不应改变数组中abs(nums[i])注意，如果x>=0，那么abs(x)等于x；否则，等于-x。示例示例1输入：nums=[1,-1,1],limit=3,goal=-4输出：2解释：可以将-2和-3添加到数组中，数组的元素总和变为1-1+1-2-3=-4。示例2输入：nums=[1,-10,9,1],limit=100,goal
本题为12月16日力扣每日一题题目来源:力扣第1785题题目tag:贪心题面题目描述给你一个整数数组nums，和两个整数limit与goal。数组nums有一条重要属性：abs(nums[i])返回使数组元素总和等于goal所需要向数组中添加的最少元素数量，添加元素不应改变数组中abs(nums[i])注意，如果x>=0，那么abs(x)等于x；否则，等于-x。示例示例1输入：nums=[1,-1,1],limit=3,goal=-4输出：2解释：可以将-2和-3添加到数组中，数组的元素总和变为1-1+1-2-3=-4。示例2输入：nums=[1,-10,9,1],limit=100,goal
