数据结构和算法 C语言实现

  第四节 子集总和 subset sum 第一节 序 斐波那契数列           Fibonacci 第二节 0 1背包问题   0 1 Knapsack Problem 第三节 编辑距离           edit distance 第四节 子集总和           subset sum 第五节 钢条切割            cut rod 第六节 硬币找零            Coin Change 第七节 最长公共子序列           Longest Common Subsequence 第八节 矩阵链式乘法 Matrix Chain Multiplication 第九节 最优游戏策略 Optimal Strategy for a Game 第十节 最优二叉查找树           Optimal Binary Search Tree 第十一节 最长递增子序列 Longest Increasing Subsequence           问题描述 给定一组非负整数和一个值sum，确定给定集合的子集是否等于sum。           例子：  输入： set [] = {3，34，4，12，5，2}，sum = 9 输出： True   有一个总和为9的子集（4，5）。 输入： set [] = {3、34、4、12、5、2}，sum = 30 输出： False 没有子集总和为30。 递归解决方案 最优子结构：从数组的右侧向左扫描，考虑两...

  第三节 编辑距离 edit distance 第一节 序 斐波那契数列           Fibonacci 第二节 0 1背包问题   0 1 Knapsack Problem 第三节 编辑距离           edit distance 第四节 子集总和           subset sum 第五节 钢条切割            cut rod 第六节 硬币找零            Coin Change 第七节 最长公共子序列           Longest Common Subsequence 第八节 矩阵链式乘法 Matrix Chain Multiplication 第九节 最优游戏策略 Optimal Strategy for a Game 第十节 最优二叉查找树           Optimal Binary Search Tree 第十一节 最长递增子序列 Longest Increasing Subsequence 问题描述 有两个字符串src和dest,通过对字符串进行最少的编辑操作将src转换为dest。 1.insert 2.remove 3.replace 以上所有操作花费均相等。 递归解决方案 从两个字符串的左侧或右侧开始处理所有字符。我们从右侧向左遍历，遍历每对字符有两种可能性。 m: Length of str1 (src string) n: Length of str2 (dest string) 1.如果两个字符串的最后一个字符相同，则无事可做。忽略最后一个字符并获得剩余字符串的计数。因此，我们将递归长度同时减1变为m-1和n-1。 2.否则（如果最后一个字符不同），我们考虑...

  第二节 0 1背包问题   0 1 Knapsack Problem 第一节 序 斐波那契数列           Fibonacci 第二节 0 1背包问题   0 1 Knapsack Problem 第三节 编辑距离           edit distance 第四节 子集总和           subset sum 第五节 钢条切割            cut rod 第六节 硬币找零            Coin Change 第七节 最长公共子序列           Longest Common Subsequence 第八节 矩阵链式乘法 Matrix Chain Multiplication 第九节 最优游戏策略 Optimal Strategy for a Game 第十节 最优二叉查找树           Optimal Binary Search Tree 第十一节 最长递增子序列 Longest Increasing Subsequence 问题描述 给定n个物品的权重(weight)和价值(value/profit)，将这些物品放在容量为W的背包中，以在背包中获得最大的总价值。注意，可以选择重量之和小于或等于背包W的物品。 问题方案 问题是要找到一些子集，以便– 1.子集中所有项目的重量总和应小于或等于背包容量 2.在满足上述条件1的所有子集中，期望的子集是其中其项的总和最大的子集。 例子: Case-1: 数量, n = 4   权重, w[] = 2 3 4 5  价值,  v[] = 3 4 5 6   背包容量, W = 5...