解题思路与方法

在这道题中，有两种常见且高效的思路：动态规划和贪心算法。

动态规划

1. 定义状态：dp[i] 表示长度为 i 的绳子剪成若干段后能得到的最大乘积。

2. 状态转移：对于 i 长度，尝试第一次剪出长度 j（1 ≤ j < i），剩下的长度为 i-j。

   • 可以继续剪剩下的绳子，此时乘积为 j * dp[i-j]

题目内容

给你一根长度为$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。

输入描述

输入为一个整数$n$，表示绳子的长度，满足 $n > 1$，代表要处理的绳子原始长度，程序需基于此长度计算剪成多段后的最大乘积。

输出描述

输出为一个整数，是将长度为 $n$ 的绳子剪成 $m$ 段（$m > 1$ 且 $m$ 为整数 ）后，各段长度相乘能得到的最大乘积结果

样例1

输入

8

输出

18