减绳子

Introduction

Question：减绳子

Analysis

一道简单的动态规划的题目。

$$
\begin{equation}
\begin{aligned}
cutRange[n] = max_{1 \le i \le n} { cutRange(i) * cutRange(n - i) } \
cutRange[1] = 1 \
cutRange[0] = 1
\end{aligned}
\end{equation}
$$

Implement

int dp[62];
int cutRope(int number) {
    // cutRope(number) = \max_{1 \le a \le number} {cutRope(a) * cutRope(number - a)}
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2;i <= number;i++) {
        dp[i] = i;
        for(int j = 1;j < i;j++) {
            dp[i] = max(dp[i], dp[j] * dp[i - j]);
        }
    }
    return dp[number];
}