动态规划剪绳子（JS 实现）

ゝ一纸荒年。 2022-05-12 09:42 180阅读 0赞

## 题目 ##

**现有一根长度为N的绳子，需要你剪成M段，使M段的乘积最大。（其中M、N都为整数，剪成的每段长度也为整数，N已知，M未知）。例如长度为8的绳子，当剪为3段乘积最大，即2\*3\*3=18.**

## 思路 ##

**看到这种求最优解的题型，你就应该思考一下动态规划是否适合。这个绳子我可以一次一次的剪，第一次剪成两段，这就变成两根新绳子，只要我分别知道这两根新绳子最大的乘积，那么我就知道了整条绳子的最大乘积了，这就将一个问题，划分为两个子问题了，且各子问题之间相互独立，满足最优子结构，因此可以使用动态规划**

**首先确定边界条件和状态转移方程：**

*  当绳子长度为1时，最大乘积为0
 *  当绳子长度为2时，可以剪成1\*1，最大乘积为1
 *  当绳子长度为3时，可以剪成（1\*2，1\*1\*1），最大乘积为2
 *  当绳子长度为4时，可以剪成（1\*1\*1\*1, 1\*2\*1, 2\*2, 1\*3），最大乘积为4
 *  当绳子长度为5时，可以剪成（1\*1\*1\*1\*1， 1\*2\*2， 3\*2, 1\*2\*1\*1, 1\*3\*1，1\*4），最大乘积为6

我们可以看到，当绳子长度n大于等于4时，`f(n) = max( f(i) * f(n-i) )`，其中`1 < i <= [n/2]`，因此我们可以用遍历来实现状态转移方程

## 代码 ##