专栏首页算法修养LeetCode 1595 Minimum Cost to Connect Two Groups of Points (动态规划)

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

题目

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

class Solution {
public:
    int dp[12][4096];
   int connectTwoGroups(vector<vector<int>>& cost) {
	int n = cost.size();
	if (n == 0)
		return 0;
	int m = cost[0].size();

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < (1 << m); j++)
		{
			dp[i][j] = INT32_MAX;
			for (int k = 0; k < m; k++)
			{
				if (j & (1 << k))
				{
					if (i != 0 && dp[i - 1][j ^ (1 << k)] != INT32_MAX )
					{
						dp[i][j] = min(dp[i][j], dp[i - 1][j ^ (1 << k)] + cost[i][k]);
					}

					if (i != 0 && (dp[i - 1][j] != INT32_MAX))
					{
						dp[i][j] = min(dp[i][j], dp[i-1][j]+cost[i][k]);
						
					}

					if (i == 0 && (j ^ (1 << k)) == 0)
					{
						dp[i][j] = cost[i][k];
					}
					else
					{
						if (dp[i][j ^ (1 << k)] != INT32_MAX)
						{
							dp[i][j] = min(dp[i][j], dp[i][j ^ (1 << k)] + cost[i][k]);
						}
					}
				}

			}
		}
	}

	return dp[n - 1][(1 << m) - 1];

}
};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    ShenduCC
  • LWC 63:746. Min Cost Climbing Stairs

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

    用户1147447
  • Leetcode【712、746、877】

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

    echobingo
  • Minimum Cost For Tickets

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

    卡尔曼和玻尔兹曼谁曼
  • 算法细节系列(18):凸包的三种计算

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

    用户1147447
  • Min Cost Climbing Stairs

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

    卡尔曼和玻尔兹曼谁曼
  • GitHub高星!互联网公司最常见的面试算法题大集合

    LeetCode是一个美国的在线编程网站,收集了各个大厂的笔试面试题,对找工作的毕业生和开发者来说,非常有价值。不过LeetCode上面的题目很多都是考察应聘者...

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

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

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

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

    N乳酸菌
  • 32类计算机与数学领域最为重要的算法

    导读: 奥地利符号计算研究所的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家,他请这些科...

    钱塘数据
  • LeetCode 664 Strange Printer

    There is a strange printer with the following two special requirements:

    用户7447819
  • leetcode-746-Min Cost Climbing Stairs(动态规划)

    chenjx85
  • 【Dr.Elephant中文文档-6】度量指标和启发式算法

    我们将作业的资源使用量定义为任务容器大小和任务运行时间的乘积。因此,作业的资源使用量可以定义为mapper和reducer任务的资源使用量总和。

    一条老狗
  • LWC 55:712. Minimum ASCII Delete Sum for Two Strings

    LWC 55:712. Minimum ASCII Delete Sum for Two Strings 传送门:712. Minimum ASCII Dele...

    用户1147447
  • 使用具有停止状态的动态对策的安全路线规划(CS.GT)

    我们考虑了定义在路线图上的经典运动规划问题,在该问题中,车辆在攻击者可以在路线图的任何边缘对车辆发起攻击的情况下,寻求从给定起始位置到给定目的地的最佳路径。车辆...

    用户7236395
  • 学习和计划未知环境中的临时扩展任务(CS)

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

    Alfred_Yip
  • Leetcode: Triangle

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

    卡尔曼和玻尔兹曼谁曼
  • hadoop-core-site.xml配置文件详解

    许喜朝
  • 机器人相关学术速递[7.8]

    【1】 RRL: Resnet as representation for Reinforcement Learning 标题:RRL:RESNET作为强化学习...

    公众号-arXiv每日学术速递

扫码关注云+社区

领取腾讯云代金券