【LeetCode】0343&剑指Offer 证书拆分&剪绳子

https://leetcode-cn.com/problems/integer-break/

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

# -*- coding:utf-8 -*-

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0]  = 1
        if n <= 2:
            return dp[n - 1]
        # 长度
        for i in range(2, n+1):
            for j in range(i):
                dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j)))
        return dp[-1]
if __name__ == '__main__':
    n = 10
    print(Solution().cuttingRope(n))

思路：简单的动态规划。类似于动态规划的钢条切割问题。