标签搜索

目 录CONTENT

文章目录

剑指offer--剪绳子.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 3 阅读 / 1,417 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

剑指offer--剪绳子

@[toc]

一、题目描述

在这里插入图片描述

二、分析

既然这道题考的是贪心,我们就用贪心来解决,不用其他的方法;

动态规划求解问题的四个特征:
①求一个问题的最优解;
②整体的问题的最优解是依赖于各个子问题的最优解;
③小问题之间还有相互重叠的更小的子问题;
④从上往下分析问题,从下往上求解问题;

  •  对于这道题,我们先确定最多可以分得的段数,对于长度为n的绳子(n > 1),如何把它分为整数长的m段(m > 1),
  •  对于m,我们最大可以分多少段?---->n段,刚好每段的长度都是1,但是这样最后分得的结果乘积为1,肯定不是最大的。
  •  所以m的最大值为绳长n的一半,因为一旦超过绳长的一半,就肯定至少有一段的长度为1,达不到结果乘积最大的目的
  •  现在长度为n的绳子最多可以分得的段数已经确定,但是我们怎么确定分为那几个段可以使结果的乘积最大呢?
  •  这里就需要才用动态规划的自下而上的求解问题的方式,在这里也算是一种枚举吧,具体点做法是:
  •  对于长度为n的绳子,我们先求出长度为1,2,3,4,....,n - 2,n - 1的绳子分为m段的最大乘积结果,那么长度为n的绳子在分为m段的最大乘积结果就肯定是分为1,2,3,4,....,n - 2,n - 1中的某一部分而已
  •  那么长度为1,2,3,4,....,n - 2,n - 1怎么求其分为m段的最大乘积呢?这不就满足动态规划的问题了吗?--整体的问题的最优解是依赖于各个子问题的最优解
  •  显然base case就是在绳长为2时和3时的情况
  •  但是当绳长为2和3也分两种情况
  •  1.绳长n大于3时,子问题:绳长为2 或者3就可以不用分段,这样可以使分段结果乘积更大。
  •  2.绳长n小于等于3时,自问题:绳长为2时,最大的结果为1,因为m是大于1 的,就是必须分段,同理当绳长为3时,最大的分段结果为2

三、代码

class Solution {
public:
    int cutRope(int number) {
    	//记录求长度为number前的子长度结果
        vector<int> dp(number + 1);
        
        // number<=3的情况,因为m>1必须要分段,例如:3必须分成1、2;1、1、1 ,
        //number=3最大分段乘积是2,
        if(number == 2)
            return 1;
        if(number == 3)
            return 2;
        
        //下面是number>=4的情况,跟number<=3不同,4可以分很多段,比如分成1、3,
        //这里的3可以不需要再分了,因为3分段最大才2,不分就是3。记录最大的。
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;

		//保存结果
        int ret = INT_MIN;
        //主要思想是每次把绳子分为j份,每次分别求最大的乘积
        //再在过程中记录最大值
       for (int i = 4; i <= number; i++) 
       {
            for (int j = 1; j <= i/2 ; j++) 
            {
            	//更新最大值,这里你只看到分为两端,一段j,另一端为i - j
            	//但是j和i - j在之前的计算中同样经历了这样的计算判断
            	//即j和i - j是分为m段中最大最优的结果
            	//所以i同样就是分为m段中最大最优的结果
                ret = max(ret,dp[j] * dp[i - j]);
            }
            dp[i] = ret;
        }
        return dp[number];
    }
};


0

评论区