网站开发怎样将信息栏到最底部,淮北论坛房产,公众号编辑器哪个好,thinkphp只能做网站Java算法之动态规划
前言
最近这一段时间一直在刷算法题#xff0c;基本上一有时间就会做一两道#xff0c;这两天做了几道动态规划的问题#xff0c;动态规划之前一直是我比较头疼的一个问题#xff0c;感觉好复杂#xff0c;一遇到这样的问题就想跳过#xff0c;昨…Java算法之动态规划
前言
最近这一段时间一直在刷算法题基本上一有时间就会做一两道这两天做了几道动态规划的问题动态规划之前一直是我比较头疼的一个问题感觉好复杂一遇到这样的问题就想跳过昨天耐着性子做了一道动态规划的题感觉没有我想象的那么难无非就是先定义dp数组然后找到初始值再写出状态转移方程一步一步来难点就是如何确定一个正确的状态这是一个一直困扰我的问题而且在写状态方程时要细心一点不要出现错误这篇文章就是记录一下自己的学习体会和心得。
动态规划的基本概念
动态规划Dynamic Programming简称DP是一种在数学、计算机科学和经济学中使用的通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构特性的问题。
动态规划的基本思想是将待求解的问题分解成若干个相互联系的子问题先求解子问题然后从这些子问题的解得到原问题的解。动态规划的关键在于正确地定义子问题以及子问题的解如何推导出原问题的解。
动态规划通常用于求解具有最优子结构特性的问题即问题的最优解可以由其子问题的最优解有效地构造出来。此外动态规划还要求子问题空间必须足够小即子问题的数量随着问题规模的增加不会增长得太快以便能够用有限的内存和时间来解决。
贪心算法
在这里我想提一下贪心算法为什么要提一下贪心算法呢因为我觉得这两个算法之间存在一些共同点。贪心算法Greedy Algorithm是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的算法。这和动态规划的将问题分解为若干个子问题求解有些类似都是从每一个小问题出发然后慢慢扩展到最后的原问题这两个算法在最优子结构特性的问题解决上都尤为有效贪心算法的优点是简单、直观且运行速度快因为每一步只关注当前状态下的最优选择而不考虑未来可能的变化。但是如果问题不满足贪心选择性质贪心算法就无法保证得到全局最优解。在这种情况下可能需要使用其他方法如动态规划。
先举一个贪心算法的小例子比如找零问题就是一个典型的贪心算法应用。假设有面值为1元、2元、5元、10元、20元、50元、100元的纸币目标是找出一个给定金额的最少纸币数。贪心策略是每次尽可能选择面值最大的纸币因为这样可以减少纸币的数量。
再举一个不满足贪心选择的性质比如贪心算法的一个经典案例背包问题背包问题有一个背包背包容量是M150。有7个物品物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大但不能超过总容量。那么运用贪心算法的思想先求出每种物品的单位价值再从最值钱的开始装直到背包装满为止。但如果对这道题修改一下不能分割物品那此时贪心算法就会失效这就是0-1背包问题。此时需要用动态规划来解决。
几道例题
1.0-1背包问题
public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);//输入商场物品的数量int N scan.nextInt();//输入小明的背包容量int V scan.nextInt();//定义两个数组分别记录商品的重量和价格int[] weight new int[N];int[] value new int[N];for (int i 0; i N; i) {//重量weight[i] scan.nextInt();//价值value[i] scan.nextInt();}//设置dp表int[][] dp new int[N1][V1];//循环遍历每一个商品每次循环都要得出在背包容量为1--V的每种情况下他所含的价值for (int j 1;jN;j){//从背包容量为1时开始遍历for(int k 1;kV;k){//如果商品容量大于背包容量那么就装不进去那么总价值就为前一个商品在这个容量的总价值if(weight[j-1]k){dp[j][k] dp[j-1][k];}//否则比较放入当前物品和不放入当前物品哪种情况价值更高else{//dp[j-1][k-weight[j-1]]这个代码是为了求减去当前商品的容量后背包的总价值再加上此时加入这个商品后的价值得到一个新的总价值如果这个总价值大于相同容量下前一个商品的价值那么就值得放入否则不值得放入dp[j][k] Math.max(dp[j-1][k-weight[j-1]]value[j-1],dp[j-1][k]);}}}System.out.println(dp[N][V]);scan.close();}
}2.爬楼梯
题目描述假设你现在正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或者2个台阶一共有多少种方法可以到达楼顶
那么对于这题很明显我们可以使用动态规划来进行求解状态很好确定首先确立边界当爬一层有多少方法当爬两层有多少种方法那么设立状态转移方程当爬第n阶时有两种状态要么现在处于第n-1个阶梯要么现在处于第n-2个阶梯那爬第n阶的方法总数就是爬n-1个阶梯的方法数加上爬n-2个阶梯的方法数。
class Solution {public int climbStairs(int n) {//当n为1时直接返回1这里返回是因为后面dp数组长度为n1如果n为1那后面对dp[2]赋值就会出现溢出if(n 1){return 1;} //设置dp数组表示爬第n阶台阶的方法数 int [] dp new int[n1];//爬第1阶台阶的方法数dp[1] 1;//爬第2阶台阶的方法数dp[2] 2;//从第三阶开始循环遍历for(int i 3;i n1;i){//状态转移方程dp[i] dp[i-2] dp[i-1];}//返回return dp[n];}}3.买股票的最佳时机 在练习数组的相关算法题时有过一道买卖股票的题但这两个题不太一样但都是用动态规划来解决的这道题要求是只能买卖一次那根据动态规划的思想每天都有两种状态一种是手里没有股票一种是手里有股票那可以设置两个边界一个是第一天手里没有股票的利润一种是手里有股票的利润然后递推下一个根据题目我们知道只能买卖一次那么如果这一天手里有股票那可能是前面买的也可能是今天买的有这两种情况比较两种的较大者作为当天有股票的最大利润。
如果当天手里没有股票那可能是前面卖的也可能是当天卖的同样我们比较两者的较大值作为当天的最大利润。
class Solution {public int maxProfit(int[] prices) {if (prices null || prices.length 0)return 0;int length prices.length;int[][] dp new int[length][2];//边界条件dp[0][0] 0;dp[0][1] -prices[0];for (int i 1; i length; i) {//递推公式dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] prices[i]);dp[i][1] Math.max(dp[i - 1][1], -prices[i]);}//毋庸置疑最后肯定是手里没持有股票利润才会最大也就是卖出去了return dp[length - 1][0];
}
}4.最大子序和 看到这道题后感觉没有什么思路后来去问了一下ai感觉茅塞顿开基本思路是定义一个dp数组这个dp数组所记录的就是以当前索引为右边界时这时候的最大子数组那么递推公式就是dp[i] nums[i] Math.max(dp[i-1],0)为什么要有这个代码呢Math.max(dp[i-1],0)这段代码是比较dp[i-1]是否大于0如果小于零那么就不能再加了因为会越加越小此时从当前索引重新开始记录为什么会越加越小呢我当时的疑问是如果当前索引是一个正数那不仍然会变大吗怎么会是越加越小呢我思索了一会想明白了以当前索引的数据来看如果加上一个负数那就会变小不如直接舍弃重新开始记录至于当前索引是正数还是负数这个不用考虑因为无论是正数还是负数加上一个负数都会变小。max Math.max(dp[i],max);这里则是记录最大值每次循环都更新max的值最后返回max。
class Solution {public int maxSubArray(int[] nums) {int length nums.length;int [] dp new int [length];dp[0] nums[0];int max dp[0];for(int i 1;ilength;i){dp[i] nums[i] Math.max(dp[i-1],0);max Math.max(dp[i],max);}return max;}
}5.打家劫舍 这道题也比较简单好理解定义一个dp数组如果不抢这一家那能获取的利润有两种情况一种是抢了前一家另一种是没抢前一家比较这两种的最大值如果抢了这一家那就只有一种情况没抢前一家的最大利润。
class Solution {public int rob(int[] nums) {int length nums.length;if(length 1){return nums[0];}//定义dp数组int[][] dp new int [length][2];//不抢第一家的利润dp[0][0] 0;//抢了第一家的利润dp[0][1] nums[0];int max 0;int mid 0;for(int i 1;ilength;i){dp[i][0] Math.max(dp[i-1][1],dp[i-1][0]);dp[i][1] dp[i-1][0]nums[i];//mid用于比较抢和不抢那种利润最大mid Math.max(dp[i][0],dp[i][1]);max Math.max(max,mid);}return max;}
}6.蜗牛 这是一道去年蓝桥杯省赛B组的真题那么解题思路如下
首先还是定义dp数组那状态如何确立确立状态就是看有几种选择那么由题可知蜗牛移动有两种方式一种是直接爬过去一种是通过传送门传送那么可以定义dp[i][0]表示到达第i个结点需要的最短时间dp[i][1]表示到达第i个传送门的最短时间。
然后就定义初始值最后写出转移方程就行了
public class Main {public static void main(String[] args) {Scanner scan new Scanner(System.in);// 在此输入您的代码...int n scan.nextInt();//定义存储竹竿x轴坐标的数组int [] x new int[n1];//定义记录每个竹竿传送门的纵坐标的数组int [] a new int[n1];//定义记录被传送到下一个竹竿的纵坐标的数组int [] b new int[n1];//输入竹竿纵坐标for (int i 1; i n; i) {x[i] scan.nextInt();}//输入传送门的位置和被传送到的位置for (int i 1; i n; i){a[i] scan.nextInt();b[i1] scan.nextInt();}double [][] dp new double[n1][2];//dp[i][0]表示到达竹竿底部的最短时间//dp[i][1]表示到达竹竿传送门的最短时间dp[1][0] x[1];dp[1][1] x[1]a[1]/0.7;for (int i 2; i n; i) {dp[i][0] Math.min(dp[i-1][0]x[i]-x[i-1],dp[i-1][1]b[i]/1.3);if(a[i]b[i]) {dp[i][1] Math.min(dp[i - 1][0] a[i] / 0.7x[i]-x[i-1], dp[i - 1][1](a[i]-b[i])/0.7);}else{dp[i][1] Math.min(dp[i - 1][0] a[i] / 0.7x[i]-x[i-1], dp[i - 1][1](b[i]-a[i])/1.3);}}System.out.printf(%.2f,dp[n][0]);}
}后记
这几天动态规划的题做的比较多其中有一些也涉及到贪心算法也了解了一下下一步我觉得应该就开始学背包问题了动态规划涉及到了0-1背包问题感觉是个很经典的问题背包问题又有很多分支0-1背包问题只是其中一个小问题还有很多问题等着我去学习看了一下去年蓝桥杯的题目感觉自己还差的有些远算法掌握的还不够多接下来就要更加努力去学习了这一个月就专心准备算法其他的事情都先放放等到蓝桥杯结束再说。
