题解 | #剪绳子#

这题首先需要注意的是 m>1, n>1. 拿到题目我是没有考虑到需要用动态规划, 后来在想暴力解的时候发现是可以用动态规划的, 于是就开始找规律. 其实动态规划的话找到状态转移方程比较重要, 但是我一开始没有去找, 而是在找规律.

n    = 2 3 4   5   6   7     8     9 
(m>=1) 2 3 2*2 2*3 3*3 3*2*2 3*3*2 3*3*3

所以我总结两个规律

1. 2和3需要尽可能的多
2. 3越多越好

比如说7, 如果只是331 = 9 < 322=12的, 而所有数字都可以使用2和3构成, 所以我就直接写代码, 在n<=3的时候特殊处理, 其余的就直接硬算, 在2 3的组合中选择3最多的, 这个思想可以得到状态转移方程:

dp(i) = 2*dp(i-2) if i-3<=1
dp(i) = 3*dp(i-3) if i-3>1

代码如下

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 
# @return int整型
#
class Solution:
    def cutRope(self , number: int) -> int:
        # write code here
        if number <= 3:
            return number - 1
        dp = [0, 0, 2, 3]
        for i in range(4, number+1):
            if i-3 <= 1:
                dp.append(2*dp[i-2])
            else:
                dp.append(3*dp[i-3])
        return dp[-1]