剑指Offer（六十七）-- 剪绳子

Github 仓库: https://github.com/Damaer/CodeSolution 笔 记 地 址： https://damaer.github.io/CodeSolution/ 仓 库 介 绍： 刷题仓库：CodeSolution

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8 时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

输入描述:

输入一个数n，意义见题面。（2 <= n <= 60）

返回值描述:

输出答案。

示例1

输入

8

返回值

18

思路以及解答

本题的解答思路就是每个长度的绳子，要么最长的情况是不剪开（长度是本身），要么长度是剪开两段的乘积。因此每个长度length都需要遍历两个相加之后等于length的乘积，取最大值。

初始化值长度为1的值为1，从长度为2开始，每一种长度都需要遍历两个子长度的乘积。

public class Solution {
    public int cutRope(int target) {
        if (target <= 1) {
            return target;
        }
        int[] nums = new int[target + 1];
        nums[1] = 1;
        nums[0] = 1;
        for (int i = 2; i <= target; i++) {
            int max = i;
            for(int j=0;j<=i/2;j++){
                int temp = nums[j]*nums[i-j];
                if(temp>max){
                    max = temp;
                }
            }
            nums[i]=max;
        }
        return nums[target];
    }
}

讲两句

剑指Offer系列到这里已经算是介绍，之后全部的题目笔记文档会同步到Github上，刷题只是兴趣，没想到自己也可以完成，算是一个Flag的完成。过两天整理出一个pdf文档，总结一下。

题目基本来源于牛客网，或许有个别题目没有，或许解法不够优，这些日后遇到会再更新。现在面试基本都需要算法，如果没有时间刷Leetcode，把剑指Offer先刷了也是一种不错的选择，基本能覆盖大部分公司的考察。

算法，我们大部分人在工作中是用不上的，普通人也几乎不会创造出一个多厉害的算法，不必为之太过焦虑，这个时代已经足够焦虑了。你可以把算法当成兴趣，或者看到文章感兴趣的时候，去看看，去试试。如果对某个题目不感兴趣，大可略过不看。

很早之前听过一句话，算法题，可以锻炼一个人知难不退的心态，能够沉下心来思考，不会觉得枯燥，当然，也是有益思维锻炼，但是它不是万能药，不能解决所有的问题，也不是一日之功。正所谓，冰冻三尺非一日之寒，滴水石穿非一日之功。

接下来主要方向：没有什么时间的话，就会日更一下LeetCode刷题，有时间的话，尽我所能深入的写某一个方向的文章/源码解析（一周一两篇长文其实已经不容易了，之前写的文章可能过于碎片化了），或许不会很高产，但是希望能尽量讲清楚，能引发自己多思考。

写文章，首先是写给自己看，然后才是面向读者。

纵使缓慢，驰而不息。

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作