钢条切割

可以将求解规模为n的原问题，划分为规模更小的子问题：完成一次切割 后，可以将产生的两段钢条看成两个独立的钢条切个问题。

组合两个子问题的最优解，并在所有可能的两段切割方案中选取组合收 益最大的，构成原问题的最优解。

钢条切割满足最优子结构：问题的最优解由相关子问题的最优解组合而 成，这些子问题可以独立求解。

钢条切割问题还存在更简单的递归求解方法

从钢条的左边切割下长度为i的一段，只对右边剩下的一段继续进行切割，左边的不再切割

递推式简化为 .png>)不做切割的方案就可以描述为：左边一段长度为n，收益为pn，剩余一段长度 为0，收益为ro=0。

.png>)

# p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

"""
2n次方

"""


def f1_recursion(p, n):
    if n == 0:
        return 0
    res = p[n]
    for i in range(1, n):
        res = max(res, f1_recursion(p, i) + f1_recursion(p, n - i))
    return res


def f2_recursion(p, n):
    if n == 0:
        return 0
    res = 0
    for i in range(1, n + 1):
        res = max(res, p[i] + f2_recursion(p, n - i))
    return res


"""
n²
重构解
"""


def cut_rod_dp(p, n):
    r = [0]
    for i in range(1, n + 1):
        res = 0
        for j in range(1, i + 1):
            res = max(res, p[j] + r[i - j])
        r.append(res)
    return r[n]


def cut_rod_extend(p, n):
    r = [0]
    s = [0]
    for i in range(1, n + 1):
        res_r = 0
        res_s = 0
        for j in range(1, i + 1):
            if p[j] + r[i - j] > res_r:
                res_r = p[j] + r[i - j]
                res_s = j
        r.append(res_r)
        s.append(res_s)

    return r[n], s


def cut_rod_solution(p, n):
    r, s = cut_rod_extend(p, n)
    ans = []
    while n > 0:
        ans.append(s[n])
        n -= s[n]
    return ans


print(cut_rod_solution(p, 7))
python
print(cut_rod_dp(p, 10))

# print(f1_recursion(p, 20))
print(f2_recursion(p, 10))