关于算法:每日一题正数分裂

给定一个负数 1，裂开的办法有一种：(1)

给定一个负数 2，裂开的办法有一种：(1，1)，(2)

给定一个负数 3，裂开的办法有一种：(1，1，1)，(1，2)，(3)

给定一个负数 4，裂开的办法有一种：(1，1，1，1)，(1，1，2)，(1，3)，(2，2)，(4)

给定一个负数 n，求裂开的办法数。

<font color=orange> 亮点：斜率优化 </font>

计划一：暴力递归

f (pre, rest)

• pre 只之前裂开的数
• rest 是本次要裂开的数。rest 要大于 pre。
• 返回后果：裂开的办法数

最终后果：f(1, n)

可能性剖析：

从左向右的尝试模型。

f(i,j) 依赖：f(i+1, rest – (i+1))+ …+ f(n, n)

def ways(n):
    return f(1, n)

def f(pre, rest):
    if rest == 0: return 1
    if rest < pre: return 0
    res = 0
    for i in range(pre, rest + 1):
        res += f(i, rest - i)
    return res

计划二：动静布局

def ways1(n):
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = 1
        dp[i][i] = 1

    for pre in range(n - 1, 0, -1):
        for rest in range(pre + 1, n + 1):
            res = 0
            for i in range(pre, rest + 1):
                res += dp[i][rest - i]
            dp

[rest] = res
    return dp[1][-1]
 计划三：动静布局 – 斜率优化 
<font color=red> 斜率优化：看看邻近的解是否替换枚举办为。</font>
def ways2(n):
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = 1
        dp[i][i] = 1

    for pre in range(n - 1, 0, -1):
        for rest in range(pre + 1, n + 1):
            dp

[rest] = dp

[rest - pre] + dp

[rest]
    return dp[1][-1]