实战 - Head of gang - 并查集 输入一串序列：Name1 Name2 Time表示A和B的通话时间，假定存在通话的人所在圈子大于2个人，认为是一个黑帮，在这个黑帮中，打电话时间最长的是老大 思路：使用并查集的思想构建节点的边关系，同时需要保存每个节点的通话时间 注意：①因为在初始化节点、边关系时，所有节点的总通话时间还不确定，所以不能过早确定边关系，等时间确定后，再确定边关系；②我的小弟的小弟还是我的小弟，所以在计算黑帮人数时，不能只计算和boss直接相关的，间接相关的也要计算上。 def headOfGang(): MAX_ = 27 father_ = ...

01背包实战 - 最小邮票数 题目要求：给定不同面额的邮票，要求我们用最少的邮票数，达到指定的面值 求解思路：该题属于典型的01背包问题，因为给定邮票张数时，相同面额也认为是单独的一张，即只有0（不拿）和1（拿）两种状态 指定面值为我们的背包容量m，给定的邮票张数为我们的物品数量n，每张邮票的价值我们认为是相同的，需要注意的是，这里要求的是最小，而不是最大，因此 需要对递推公式进行修改，这里我们直接采用空间优化后的方法 递推公式：dp[j] = min(dp[j], dp[j - weight[i]] + value[i] 难点分析：①无解的判断：将dp数组初始化为无穷大，若最后dp[m]为...

采药问题属于01背包问题 采用动态规划进行求解： 保存结果：dp[i][j]表示前i件物品放入容量为j的背包，所能带来的最大价值 递推公式：①如果第i件物品不放入背包，那么就代表我们要放的是前i - 1件物品 => dp[i][j] = dp[i - 1][j]；②如果第i件物品放入背包，那么第i件物品的价值value[i]我已经获得了，除此以外，我还有j - weight[i]的空间可以放我们的前i - 1件物品；综上，可得递推公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i] 空间优化：注意到上面的...

点菜问题属于背包问题中的01背包 物品是一个整体，两个状态，放或不放，因此得名01背包 有n个物品，背包容量为m，每个物品有重量w和价值v，要求放入背包中的物品价值最大 保存结果：dp[i][j]表示前i个物品放入容量为j的背包的最大价值 递推起点：dp[0][j] = dp[i][0] = 0（同时也是边界值） 递推公式：①如果第i件物品放进去，背包剩余容量为j - w[i] => dp[i][j] = dp[i - 1][j - w[i]] + v[i]; ②如果第i件物品不放进去，背包剩余容量为j => dp[i][j] = dp[i - 1][j]; 综...

最长公共子序列 题目要求：对字符串S1（长度为n）和S2（长度为m）求公共子串S3，并且S3的长度最大，求该长度 动态规划分析： 保存结果：dp[i][j]表示以S1[i]结尾和S2[j]结尾的最长公共子序列的长度 递推起点： dp[i][0] = 0; dp[0][j] = 0;（同时也是边界值处理） 递推公式： ①如果S1[i] == S2[j] => dp[i][j] = dp[i - 1][j - 1] + 1 ②如果S1[i] != S2[j] => dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 最终解为：dp[n - 1][m -...

合唱队形 题目要求：现有N名同学，求至少需要让多少名同学出列，使得现有的同学不需要调整就可以形成合唱队形，即中间高两边低 思路：求一个最长递增子序列和一个最长递减子序列，然后两者交集 代码： def chorusFormation(): # 求最长递增子序列 def maxAscSubSeq(end): inde = [0 for i in range(num + 1)] for i in range(end + 1): inde[i] = 1 for j in range(i): ...