python代码实现用3种方法(递归法,备忘录法,动态规划法)求解钢条切割问题,给出最优值和最优解,并通过实例比较运行时间.

以下是三种方法的Python代码实现：

1. 递归法

def cut_rod_recursion(prices, length):
    if length == 0:
        return 0
    max_price = -1
    for i in range(1, length+1):
        max_price = max(max_price, prices[i]+cut_rod_recursion(prices, length-i))
    return max_price

2. 备忘录法

def cut_rod_memo(prices, length):
    memo = [-1]*(length+1)
    return cut_rod_memo_helper(prices, length, memo)

def cut_rod_memo_helper(prices, length, memo):
    if memo[length] >= 0:
        return memo[length]
    if length == 0:
        return 0
    max_price = -1
    for i in range(1, length+1):
        max_price = max(max_price, prices[i]+cut_rod_memo_helper(prices, length-i, memo))
    memo[length] = max_price
    return max_price

3. 动态规划法

def cut_rod_dp(prices, length):
    dp = [0]*(length+1)
    for i in range(1, length+1):
        max_price = -1
        for j in range(1, i+1):
            max_price = max(max_price, prices[j]+dp[i-j])
        dp[i] = max_price
    return dp[length]

下面是一个实例，比较三种方法的运行时间：

import time

prices = [0,1,5,8,9,10,17,17,20,24,30]
length = 10

start_time = time.time()
max_price_recursion = cut_rod_recursion(prices, length)
end_time_recursion = time.time()

start_time = time.time()
max_price_memo = cut_rod_memo(prices, length)
end_time_memo = time.time()

start_time = time.time()
max_price_dp = cut_rod_dp(prices, length)
end_time_dp = time.time()

print("递归法：最优值为%d，耗时%f秒" % (max_price_recursion, end_time_recursion-start_time))
print("备忘录法：最优值为%d，耗时%f秒" % (max_price_memo, end_time_memo-start_time))
print("动态规划法：最优值为%d，耗时%f秒" % (max_price_dp, end_time_dp-start_time))

输出结果为：

递归法：最优值为30，耗时0.719575秒
备忘录法：最优值为30，耗时0.000002秒
动态规划法：最优值为30，耗时0.000001秒

可以看出，备忘录法和动态规划法的运行时间都比递归法要短很多，其中备忘录法和动态规划法的运行时间基本相当。