专栏首页算法修养LeetCode 1547. Minimum Cost to Cut a Stick(动态规划)

LeetCode 1547. Minimum Cost to Cut a Stick(动态规划)

题目

区间DP,由于棍子长100万,所以我们在cuts之间做区间DP。

那么状态转移方程就是很简单直白的区间DP

dp[i][j] = min { dp[i][k-1] + cost(k) + dp[k+1][j]} i<=k<=j

cost(k) 表示 从k处切断的cost

class Solution {
public:
   
int dp[105][105];
int getLen(int i, int j, vector<int>& cuts, int n)
{
	int left = i == 0 ? 0 : cuts[i-1];
	int right = j == cuts.size() - 1 ? n : cuts[j+1];
	return right - left;
}

int minCost(int n, vector<int>& cuts) {

    sort(cuts.begin(),cuts.end());
	memset(dp, 0, sizeof(dp));
	for (int l = 0; l < cuts.size(); l++)
	{
		for (int i = 0; i + l< cuts.size(); i++)
		{
			int j = i + l;
			if (i == j)
			{
				dp[i][i] = getLen(i,j, cuts, n);
			}
			else
			{
				dp[i][j] = INT32_MAX;
				for (int k = i; k <= j; k++)
				{
					dp[i][j] = min(dp[i][j], (k==0?0:dp[i][k - 1]) + getLen(i, j, cuts, n) +  dp[k + 1][j]);
				}
			}	
		}
	}

	return dp[0][cuts.size() - 1];
}
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1595 Minimum Cost to Connect Two Groups of Points (动态规划)

    题解: 动态规划,用二进制压缩状态,注意分析几种情况,就能推出来正确的状态转移方程。

    ShenduCC
  • Minimum Cost For Tickets

    In a country popular for train travel, you have planned some train travelling on...

    卡尔曼和玻尔兹曼谁曼
  • Leetcode【712、746、877】

    读完题目后发现:把两个字符串中多余的字符删除后,最后留下的字符串是两个字符串的最长公共子序列。因此这道题可以像最长公共子序列一样,采用动态规划的思想解决:常考的...

    echobingo
  • LWC 63:746. Min Cost Climbing Stairs

    Problem: On a staircase, the i-th step has some non-negative cost cost[i] assig...

    用户1147447
  • 448页伊利诺伊大学《算法》图书【附PDF资料】

    本书是Jeff Erickson即将出版的免费电子教科书《算法》,以及他自1998年以来为伊利诺伊大学厄巴纳香槟分校各种计算机理论课程撰写的其他课堂讲义笔记。

    马上科普尚尚
  • Leetcode: Triangle

    最近都在复习英语,看见看得头都大了,而且阅读越做分数越低!换个环境,做做Leetcode试题!

    卡尔曼和玻尔兹曼谁曼
  • 学习和计划未知环境中的临时扩展任务(CS)

    我们提出了一种新颖的计划技术,可以满足部分显示环境中时态逻辑中指定的任务。我们定义了从环境和给定任务本身派生的高级操作,并估计每个操作如何有助于完成任务。如图所...

    Alfred_Yip
  • 原来还有这样的记词方法_Java版记不规则动词_博主推荐

    昨天在看一本英语书的不规则动词的时候,突然产生的灵感:就是想把这样记单词简单方式,用程序代码实现,然后,使用户可以与之进行交互

    Hongten
  • LeetCode 63、64 动态规划两题连刷,移动坐标的小技巧

    今天是LeetCode的37篇,趁着周末,开始我们愉快的刷题。今天要刷的题目是LeetCode 63和64两题,分别是Unique Paths II和Minim...

    TechFlow-承志
  • Code Forces 18D Seller Bob(简单DP)

    D. Seller Bob time limit per test 2 seconds memory limit per test 128 mega...

    ShenduCC
  • Min Cost Climbing Stairs

    On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 ind...

    卡尔曼和玻尔兹曼谁曼
  • ROS和RRT的一些资料

    ROS和RRT结合的示例比较多,之前博文提过两次( 1 和 2 ),本文做一些汇总和整理,大部分都在roswiki和GitHub上有具体说明。需要认真阅读源码和...

    zhangrelay
  • 当你做不到的时候该怎么做:软时序逻辑约束下的时序逻辑规划(CS)

    译文:本文考虑一个时序逻辑规划问题,其目标是在满足用线性时序逻辑(LTL)表示的软规范集中找到一个满足最优选择的无限轨迹,同时满足用LTL表示的硬规范。我们之前...

    N乳酸菌
  • ​LeetCode刷题实战120: 三角形最小路径和

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 算法细节系列(18):凸包的三种计算

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode笔记:Weekly Contest 201 比赛记录

    第一题看似有点复杂,但是终究是一道easy的题目,我们只需要注意例二中给出的情况,即在删除了bB之后,后面的A需要与上一个a进行比较,因此,这道题目就是一个比较...

    codename_cys
  • 132. 分割回文串 II

      str = “ABA”,str本身就是回文串,返回0.   str = “A|CDCDC|DAD”,最少需要切两次变成3个回文子串,所以 返回2.

    程序员小王
  • leetcode-746-Min Cost Climbing Stairs(动态规划)

    chenjx85
  • 用python讲故事(下)

    从排序(歌曲,然后发生了点什么)到英雄的幸福的大驼峰,随后是阴暗的山谷。 我们检测到某种电影/故事的迪斯尼公式吗? 当绘制线在不同长度上发生时,很难比较这些曲线...

    哒呵呵

扫码关注云+社区

领取腾讯云代金券