343整数拆分

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def integerBreak(self, n: int) -> int:
        # 动态规划，设定d[i] 为将i拆分后，能够得到的最大乘积数；
        # 拆成两个是 j*(i-j); 拆成三个以及三个以上是 j*d[i-j]，因为 d[i-j]递归拆下去至少是两个;
        # 初始化
        d = [0 for _ in range(n+1)]
        d[0],d[1],d[2] = 0,0,1
        for i in range(3,n+1):   # 对每一个i 都试着切分，取出最大的结果。
            for j in range(1,i):
                d[i] = max(d[i],j*(i-j),j*d[i-j])
        return d[n]