切割成本

[编程题]切割成本

热度指数：1391 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将一条长度为x的线段切成若干段，切割点已给出，每次切割的成本为切割后产生的两段线段长度之和，求最小的切割成本。

示例1

输入

20,[2,5,10,18]

输出

说明

线段长为20，切割点为[2,5,10,18]。
第一种方案：
1.先切开第一个点，成本为2+18=20
2.切开第二个点，成本为3+15=18
3.切开第三个点，成本为5+10=15
4.切开第四个点，成本为8+2=10
总成本为：20 + 18 + 15 + 10 = 63;
第二种方案：
1.先切开第一个点，成本为5+15=20
2.切开第二个点，成本为2+3=5
3.切开第三个点，成本为5+10=15
4.切开第四个点，成本为8+2=10
总成本为：20 + 5 + 15 + 10 = 50;

备注:

切割点个数<300
x<1000000

算法知识视频讲解

Python 3

ZhongHaoWang

经典的区间dp

class Solution:
    def attackMonster(self , n , cuts ):
        # write code here
        m = len(cuts)
        cuts = [0] + sorted(cuts) + [n]
        dp = [[0 for i in range(m + 2)] for i in range(m + 2)]

        for i in range(m, 0, -1):
            for j in range(i, m + 1):
                if i == j:
                    dp[i][j] = 0
                else:
                    dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j] for k in range(i,j + 1))
              
                dp[i][j] += cuts[j + 1] - cuts[i - 1]
        
        return dp[1][m]

发表于 2021-08-28 16:55:46 回复(0)