343. 整数拆分 | 暴力求解 | 暴力递归 | 动态规划 | 自顶向下分析

力扣打卡:343. 整数拆分

解题思路

可能思路不是很好想到

  • 大于1的每一个数至少分成 1 + n-1 | 2 + n-2 | ...
  • 根据上面的分解,每一个大于1的数都可以分解成至少两个整数,那么这两个分解生成的两个整数如果同样属于大于1的这个范围
  • 那么可以继续分解,此时每一个数都可以分解成 2个 或者 n个 的数字的和
  • 如果从两个开始分,2,3,4,5,6 …分解下去,总是能找到乘积最大的时候

流程

  • 函数先分解成两个数 for(int i=1; i<n; i++)1+n-1 | 2+n-2 等等
  • 定义一个函数,能得到这个数的各种分解中的最大乘积 int subAns = planA(n-i)
  • 这个最大的乘积和当前这个数进行比较,选择较大的一个 int subMax = Math.max(n-i, subAns)
  • 记录下 选择出来的较大值两个数的各种分解中的分解的较大值, 取较大的值 max = Math.max(max, i * subMax);
  • 最后返回这个较大的值即可

举个例子

给定一个数 10

  • 这个数可以按照两个数的分解:分解成 1 + 9 | 2 + 8 | 3 + 7 | 4 + 6 | 5 + 5 | 6 + 4 | 7 + 3 等等
  • 此时每一个大于 1 的数字又可以进行分解成两个数,i + n-i i 从 1 开始,那么到最后一定可以分解到各种组合
  • 写递归函数,弄清楚递归函数的定义,然后将这个定义给出的结果进行使用,然后联系当前状态和子状态,最后返回就可以得到结果了
  • 定义一个函数,可以得到每一个数的各种分解中的最大乘积(注意:一般题目要求的就是我们需要定义递归函数的返回)
  • 第一次得到 9 的各种分解的最大乘积值,与 9 进行比较,取大值 subMax,不一定是各种分解中的最大值,不分解可能更大,取大值即可
  • 然后与初始的 max 进行 取大值的比较 Math.max(max, i * subMax),注意此时的是 i * subMax ,此时的max记录大值
  • 第二次得到 8 的各种分解的最大乘积值,与 8 进行比较,取大值 subMax,不一定是各种分解中的最大值,不分解可能更大,取大值即可
  • 然后与 9 的最大乘积值进行比较,取大值即可
  • 依次类推,能够这样分解的愿意就在于分解成两个数之后,还可以再进行分解,这个也是这个题目难理解的地方
  • 只要理解清楚了,和平常的题目就一样,写出了暴力递归,那么自顶向下的动态规划,也就是多了判断和记录的两个过程

代码

class Solution {
    public int integerBreak(int n) {
        // 理解原理: 每一个数都可以分解成 1 + n-1 | 2 + n-2 | 3 + n-3 ....
        //          同时这其中的n-1,n-2,n-3又可以重新分为小于其的最大整数和1,依次类推
                    // 需要考虑的是:这些数可以一直分解,直至小于2时,不能分解成两个整数的和了,那么停止
                    // 也就是说

        // 这也就是说明了,只需要考虑两个数的情况就可以了,不需要考虑分解成三个或者是分解成四个这种场景
        // 因为每个数分解成两个数之后,这两个数的又可以分解成两个数,然后再次分解成两个数,最后在范围内的分解都存在


        // 那么定义一个函数,能够得到给定的数的最大乘积

        // return planA(n);

        int[] memo = new int[n+1]; // 需要n+1的长度进行储存数据n
        return planB(n, memo);
    }   

    public int planA(int n){
        if(n < 2) return 0; // 当 n 已经小于 2, 此时不能再进行分解了, 也就是返回0

        int max = 0; // 初始化为0
        for(int i=1; i<n; i++){
            
            int subAns = planA(n-i);
            
            int subMax = Math.max(n-i, subAns);
            
            max = Math.max(max, i * subMax);
        }

        return max;
    }

    // 写出了暴力递归的方式,那么自顶向下的动态规划也就是多了判断和记录的两个过程
    public int planB(int n, int[] memo){
        if(n < 2) return 0; // 如果此时的n小于2,那么不能再进行分解了
        if(memo[n] != 0) return memo[n];

        int max = 0;
        for(int i=1; i<n; i++){
            int subAns = planB(n-i, memo);
            int subMax = Math.max(n-i, subAns); //  这里的意思是指: n-i 的大小 和 n-i 分解成某一些数字后的乘积的大小的对比
            max = Math.max(max, i * subMax);
        }
        memo[n] = max;
        return memo[n];
    }
}
上一篇:斐波那契数(Java)


下一篇:LeetCode今日刷题2021/07/01