欢迎大家来到IT世界,在知识的湖畔探索吧!
递归解决问题是自顶向下，一直从最大的问题递归至小问题，只有小问题解决了，一层一层地返回，便可以得到最终的结果。这里会有很多重复的计算。
动态规划是比递归性能好，因为它会把小问题的计算结果保存在dp数组中，计算更大的问题时会用到小问题的结果，直接调用而不必重新计算。解决问题是一个自底而上的思路。
贪心算法是动态规划问题中的局部最优问题解，不要遍历当前子问题中的所有情况，一般只取当前最优情况。
例如数组[-6,4,-3,5,-1,-2,1,-3,4]，连续子数组[4,-3,5]的最大值为6
public int maxSubArray(int[] arra) { int n = arra.length; //一般一位数组或二维数组dp保存已经计算过得值，备忘录法 int[] dp = new int[n]; dp[0] = arra[0]; int max = dp[0]; for(int i = 1; i < n; i++){ dp[i] = arra[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0); max = Math.max(max, dp[i]); } return max; }欢迎大家来到IT世界,在知识的湖畔探索吧!
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/91626.html
