使用切绳子问题详解分治法、动态规划法和贪婪算法

不多bb，直接上代码

/**1. 以剑指Offer的切绳子问题为例，演示回溯法、动态规划法、贪婪算法的基本思想，以及它们之间的区别*/
public class Algorithms {public static void main(String[] args) {int lengthOfScope = 13;System.out.println("dynamicProgramingAlgorithm：" + dynamicProgramingAlgorithm(lengthOfScope));System.out.println("divideAndConquerAlgorithm：" + divideAndConquerAlgorithm(lengthOfScope));System.out.println("greedyAlgorithm：" + greedyAlgorithm(lengthOfScope));}/**动态规划算法的四个特征* 1. 用于求问题的最优解（最大值/最小值）* 2. 整体问题的最优解依赖于各子问题的最优解* 3. 原问题分解得到的若干子问题，子问题继续分解得到更小的子问题，这些小问题之间有重叠的问题（重叠问题越多，动态规划算法相对于分治法的效率越高）* 4. 从上往下分析问题，从下往上解决问题*//**动态规划法解决切绳子问题（常规思路）* 1. 使用数组arr保存子问题1、2、3...的结果，数组长度为问题个数（包括原问题）* 2. 计算顺序从下往上，即先根据arr[0]计算arr[1]，再根据arr[1]计算arr[2]，依此类推，直到arr[length-1]* 3. 返回arr[length-1]，既为原问题求解结果* 4. arr[0]为基本问题，不可再分，可以通过分析得到* 5. 动态规划法解决切绳子问题的时间复杂度为O(n^2)*/public static int dynamicProgramingAlgorithm(int length){//绳子长度为0、1、2、3时，由于规定必须切一刀，按特殊情况处理if(length <= 1){return 0;}else if(length == 2){return 1;}else if(length == 3){return 2;}else{//当绳子长度大于等于4时，开始动态规划int[] arr = new int[length+1];arr[1] = 1;arr[2] = 2;arr[3] = 3;for(int i=4;i<arr.length;i++){int max =0;for(int j=2;j<=i/2;j++){//每次内层循环计算绳子切一刀的乘积，若result > max，则更新max值int result = arr[j] * arr[i - j];if(result > max){max = result;}}//每次外层循环得到长度为i的绳子的分段乘积最大值，并保存到数组arr中arr[i] = max;}//最终返回长度为length的绳子的分段乘积最大值return arr[length];}}/**分治法* 1. 分治法是递归思想的典型应用* 2. 将原问题分解为若干个子问题，再将子问题分解为更小的若干子问题，直到基本问题，最终解决原问题* 3. 当分解的子问题中有大量重叠的子问题时，分治法的效率会大大降低，如牛客网上减绳子的分治解法无法通过*//**对比分治法和动态规划法* 1. 分治法使用递归依次求解所有子问题，即使子问题有重叠；动态规划法将子问题的结果保存在数组中，重叠的子问题不重复计算* 2. 分治法从上往下计算，动态规划法从下往上计算* 3. 相同点：基本思想都是把原问题分解为子问题求解，动态规划法只是把分治法的子问题结果保存起来，避免重复计算* 4. 当有重叠子问题时，使用动态规划法，否则使用分治法*/public static int divideAndConquerAlgorithm(int length){//绳子长度为0、1、2、3时，由于规定必须切一刀，按特殊情况处理if(length <= 1){return 0;}else if(length == 2){return 1;}else if(length == 3){return 2;}else{return Max(length);}}public static int Max(int length){if(length == 1){return 1;}else if(length == 2){return 2;}else if(length == 3){return 3;}else{int max = 0;//使用循环找出绳子长度为length时分段乘积的最大值，并返回for(int i=1;i<=length/2;i++){int result = Max(i)*Max(length-i);if(result > max){max = result;}}return max;}}/**贪婪算法* 1. 在对问题求解时，总是做出在当前看来是最好的选择。不是从整体最优上考虑，而是在每一步都去求局部最优解* 2. 贪婪算法不能保证得到全局最优解，最重要的是选择一个合适的贪婪策略* 3. 贪婪算法能大大降低时间复杂度，是一个简单同时还能得到比较不错结果的算法* 4. 贪婪算法在切绳子问题的体现：当长度大于5时，每次都切下来长度为3的绳段，直到剩下绳子长度小于5* 5. 使用贪婪算法解决切绳子问题的时间复杂度为O(1)*/public static int greedyAlgorithm(int length){if(length <= 1){return 0;}else if(length == 2){return 1;}else if(length == 3){return 2;}else {int remainder = length%3;int numOf3 = length/3;int max = 0;switch (remainder){case 0:max =  (int) Math.pow(3,numOf3);break;case 1:--numOf3;max = (int) Math.pow(3,numOf3)*4;break;case 2:max = (int) Math.pow(3,numOf3)*2;break;}return max;}}
}

以上均为个人见解，如有谬误，欢迎指正！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！