【题14 剪绳子】Java实现

左手的ㄟ右手 2022-03-28 19:24 158阅读 0赞

动态规划和贪婪算法

> 动态规划  
> 求一个问题的最优解（最大值或最小值），而且该问题能够分解成若干子问题，并且子问题之间还有重叠的更小的子问题，可以考虑动态规划  
> （1） 分析是否能把大问题分解成小问题  
> （2） 分解后的每个小问题存在最优解  
> （3） 小问题的最优解组合起来能得到整个问题的最解

> 贪婪算法求解：  
> 每一步都可以做出一个贪婪的选择，基于这个选择，确定能够得到最优解  
> 1． 贪心算法在对问题求解时，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。  
> 2． 选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关  
> 3． 题目贪心策略：当n>=5时，尽可能多地剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子

动态规划与贪心算法题目整理见

**【题目】**  
给你一个长度为n的绳子，请把绳子剪成m段（m，n都是整数。n>1并且m>1）.每段绳子的长度记为k\[0\],k\[1\],…k\[m\],请问k\[0\]\*k\[1\]….k\[m\]。可能的最大乘积是多少？  
例如：当绳子的程度是8时，我们把它剪成长度分别为2，3，3的三段，此时得到的最大乘积为18.

**有两种不同解法**  
（1） 常规的需要O(n^2)时间和O(n)空间的动态规划思路。  
（2） 接着用O(1)时间和空间的贪婪算法来分析解决问题。  
**动态规划求解：**  
**分析：**  
（1）目标是求剪出各段绳子乘积的最大值f(n)。求一个问题的最优解——**特点1**.  
（2）第1刀放在长度为i（0<i<n）的位置，把绳子剪成i和n-i两段，用最优化的方法把长度为i和n-i的两段分别剪成若干段，使各段剪出的乘积最大，得到整个问题最优解f(n),即整体最优解依赖各个子问题最优解——**特点2**  
（3）把大问题分解成若干小问题，这些小问题之间还有互相重叠的更小的子问题——**特点3**  
（4）子问题在分解大问题的过程中重复出现，为了避免重复求解子问题。  
我们可以从下往上顺序先计算小问题最优解并存储下来，以此为基础求大问题最优解，从上往下分析问题，从下往上求解问题——**特点4.**  
每一步都面临若干选择： **f(n) = max(f(n) \* f(n-i)) 0<i<n**

**方法：**  
定义函数f(n)把长度为n的绳子剪成若干段后各段长度乘积的最大值，剪第一刀，有n-1种可能选择，f(n) = max(f(n) \* f(n-i)) 0<i<n  
这是从上至下的递归公式，按照从下而上顺序计算，f(2),f(3), f(4),f(5) 得到f(n)  
当绳子长度为2时，剪成长度为1 的两端，f(2) = 1  
当绳子长度为3时，剪成长度分别为1，2，的两段或者都为1的三段，1*2>1*1\*1 f(3) = 2

**贪婪算法求解：**  
每一步都可以做出一个贪婪的选择，基于这个选择，确定能够得到最优解  
**分析：**  
如果绳子的长度大于5，则每次都剪出一段长度为3的绳子  
如果剩下的绳子长度仍然大于5，则接着剪出一段长度为3的绳子，  
接下来，重复这个步骤，直到剩下的绳子长度小于5，  
剪出一段长度为3的绳子，就是每一步做出的贪婪选择。

按照下面的策略来剪绳子，得到各段绳子的长度的乘积将最大  
当n>=5 尽可能多地剪长度为3的绳子。  
当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。  
**实现**

package ti14;
    
    public class Lian {
    	//动态规划
    	public static int getMaxResult(int length) {
            
            int[] res = null ;
            int max = 0 ;
            
            if(length < 2 ) {
                return 0 ;
            }
            
            if(length == 2) {
                return 1 ;
            }
            
            if(length == 3) {
                return 2 ;
            }
            
            res = new int[length+1] ;
            res[0] = 0 ;
            res[1] = 1 ;
            res[2] = 2 ;
            res[3] = 3 ;
            
            for(int i = 4 ; i <= length ; i ++) {
                max = 0 ;
                for(int j = 1 ; j <= i/2 ; j++) {
                    
                    int r = res[j] * res[i-j] ;
                    
                    if(max < r) {
                        max = r ;
                        res[i] =max ;
                    }
                    
                }
                
            }
            
            max = res[length] ;
    
            return max ;
            
        }
    	//贪婪算法
    	public static int getMaxResult1 (int length) {
        
    		if(length < 2 ) {
    			return 0 ;
    		}
        
    		if(length == 2) {
    			return 1 ;
    		}
        
    		if(length == 3) {
    			return 2 ;
    		}
        
    		int timesOf3 = length/3 ;
    		if(length - timesOf3*3 == 1) {
    			timesOf3 -= 1 ;
    		}
        
    		int timesOf2 = (length - timesOf3*3)/2 ;
        
    		return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2)) ;//Math.pow(x,y)返回值:x 的 y 次幂
    	}
    	
    	//测试
    	public static void main(String[] args) {
            
            long curTime = System.nanoTime() ;
            
            System.out.println(getMaxResult(1));
            System.out.println(getMaxResult(3));
            System.out.println(getMaxResult(8));
            System.out.println(getMaxResult(50));
            System.out.println(System.nanoTime() - curTime);
            System.out.println("**************************************************");
            curTime = System.nanoTime() ;
            System.out.println(getMaxResult1(1));
            System.out.println(getMaxResult1(3));
            System.out.println(getMaxResult1(8));
            System.out.println(getMaxResult1(50));
            System.out.println(System.nanoTime() - curTime);
        }
    }

**注**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]

参考：  
1.《剑指offer》  
2.[https://www.jianshu.com/p/43acdf2f23c5][https_www.jianshu.com_p_43acdf2f23c5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220328/0a59c61f3d004befb474578f41d051d5.png
[https_www.jianshu.com_p_43acdf2f23c5]: https://www.jianshu.com/p/43acdf2f23c5