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

不多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;
        }
    }
}

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

本文地址：https://blog.csdn.net/qq_41131223/article/details/109275912