精选留言(102)

• 
  阿信

  2019-06-11

  编辑距离，刚开始没看太明白。后台看了下其他的博客，结合一起进行理解。表格里面min三个数值为： d[i, j]=min(d[i-1, j] + 1, d[i,j-1]+1, d[i-1,j-1]+r(i,j)) 涉及两个数组，是二维的。描述了从垂直、水平、斜对角 三个方向分别到达(i, j)这个位置时的距离。 我是先看懂了后面的推导公式，再看明白编辑推导表格。

  展开

  

  19
• 
  cwtxz

  2019-12-28

  中国程序员的最大阻碍是语言障碍，英语不好，无法和世界各地的人交流技术，坐井观天的人很多。第二个严重的问题就是学习能力不强而且没有毅力，很容易放弃，不肯花时间深入思考问题和钻研，大多思考如何能少加班，如何能赚更多，如何在工作中偷懒等等。第三个问题就是好高骛远不能脚踏实地，很多人刚毕业就想要很多钱，换一份工作就想涨很多钱，但是能力不够，基础不扎实，有些连在简历中写的技术都说不清楚。曾经我是他们中的一员，但是我想改变去，不想继续平庸下去，所以，我来了，加油，坚持坚持再坚持!!!

  展开

  作者回复: 我很佩服你有如此的思考，坚信自己选择的方向，从脚下的路开始，你一定会得到属于自己的成功

  共 3 条评论

  13
• 
  Joe

  2019-01-14

  1.C++实现，对总金额100的最小纸币是15. 2.用递归法总金额为30就要算很久。 3.另外的数学办法可以用总金额依次对最大金额纸币求余数，直到为0.商相加为答案。如：若 {1, 2, 3, 7}为纸币金额，对于100，所需最小纸币数：100/7=14余2; 2/2 = 1余0;则纸币数为14+1=15. // 动态规划问题 #include <iostream> #include <string> #include <vector> using namespace std; class DynamicProgramming { private: vector<int> money = {1, 2, 3, 7}; // 纸币种类 public: /** * Description: 对于金额固定，找出最少钱币数及方式。 * prams: amountMoney- 输入总金额 * return: 所需最小纸币数 */ int findFewerstMethod(int amountMoney) { int c[amountMoney]; c[0] = 0; int temp; for (unsigned int i = 1; i < amountMoney; i++) { // 用最大值初始化 int tempMin = amountMoney; for (unsigned int j = 0; j < money.size(); j++) { int diff = i - money[j]; if (0 <= diff) { temp = c[diff] + 1; } else { // 此情况表示该纸币无效，选择最大值。 temp = amountMoney; } // 求出最小值 if (temp < tempMin) { tempMin = temp; } } c[i] = tempMin; } return c[amountMoney - 1]; } }; // test int main(void) { DynamicProgramming test; int res = test.findFewerstMethod(100); cout << res << endl; return 0; }

  展开

  作者回复: 答案正确 👍

  共 4 条评论

  13
• 
  云开

  2019-01-31

  还是弄不明白编辑距离 为什么插入时是从空串开始 替换确并不计算从空串到有字符的过程

  作者回复: 你可以参考那张状态转移表，看看是从哪一格到哪一格，字符串是如何变换的，相邻格子的变换就三种方式，插入、删除和替换。替换可以将字符串中的某个字符替换成另一个字符

  

  12
• 
  冰木

  2019-01-26

  老大，我可能没有得到要领，可以推到下，表格中，第一行，第二列吗？

  作者回复: 是min(3, 1, 2)对吧，这个是mo和m的比较，3表示增加一个m再增加一个o，再删掉一个o，编辑距离是2+1=3。1表示两个字符串都是m，其中一个再增加一个o，编辑距离是1。2表示一个m增加o，一个从空集到m，编辑距离是2。你可以顺着第9讲最后的表格来推导。

  共 2 条评论

  9
• 
  梅坊帝卿

  2019-01-04

  按照面值排序优先取最大的方法 不一定能取到解 除非有万能的面额1 比如 2 5 7 总数15

  作者回复: 是的 可能无解👍

  

  6
• 
  予悠悠

  2019-01-22

  用python交作业 用递归来实现时，运行非常慢。用循环实现时，由于记录了每一步的计算结果，不需要重复计算，速度快很多。 递归： import sys def least_bills_recursion(total): if total == 0: return 0 if total < 0: return sys.maxint min_bills = min(1 + least_bills_recursion(total-2), 1 + least_bills_recursion(total - 3), 1 + least_bills_recursion(total-7)) return min_bills 循环： def least_bills_iteration(total): current = 0 dp = [0] * (total + 1) dp[2] = 1 dp[3] = 1 dp[7] = 1 for i in xrange(3, total+1, 1): if i >= 7: dp[i] = min(dp[i-2], dp[i-3], dp[i-7]) + 1 elif i >= 3 and i < 7: dp[i] = min(dp[i-2], dp[i-3]) + 1 else: dp[i] = dp[i-2] + 1 return dp[total] 当总金额为100时，答案为15.

  展开

  作者回复: 实现了两种方法，并进行了对比，赞👍

  共 2 条评论

  5
• 
  caohuan

  2019-01-21

  本篇所得： 1.求解 最值可用动态规划 方法; 2.状态转移 可以把 大问题 分解为 小问题，再分解为 可以处理的问题，即 把 不可以处理的问题 分解为可以 处理的小问题（ 也为子问题）; 3.动态规划 适用于 下一个 状态与上一个状态有固定关系; 4.搜索引擎的 搜索词的查询推荐， 英文可用 编辑距离，中文 需要 转化 比 如转为英文 再使用 编辑距离; 5.从问题开始 ，初步分解 大问题为可解的子问题 为动态规划的方法，由问题 推到答案，也为反向思维法。 回答老师的问题：固定金额，找最小钱币数量，可用倒推法，总金额 减去 最大的 钱币数额 ，然后从钱币中寻找该数额，没有 再把该数额逐渐减去 大的数额，一步步分解，可得 钱币的数量，该方法是 动态规划，但不能保证寻找的是最小的数量，局部最优 不一定全局最优，如果 需要寻找全部最优 需要运用 排列和组合。

  展开

  共 1 条评论

  5
• 
  我心留

  2019-01-05

  public class Lesson10_2 { /** * 动态规划求最小钱币数 * @param c 用一维数组记录每一步的总金额 * @param value 用一维数组记录三种面额的纸币 * @return */ public static int getMinMoney(int[] c, int[] value) { int[] t = new int[3]; for (int i = 0; i < c.length; i++) { for (int j = 0; j < value.length; j++) { if (i - value[j] >= 0) { t[j] = c[i - value[j]] + 1; } } int min = Math.min(t[0], t[1]); min = Math.min(min, t[2]); c[i] = min; } return c[c.length - 1]; } public static void main(String[] args) { int[] c = new int[100]; int[] value = new int[] { 2, 3, 7 }; System.out.println(getMinMoney(c, value)+1); } } 老师看一下代码对吗，运行结果是15

  展开

  作者回复: 代码的逻辑是对的

  共 2 条评论

  4
• 
  lianlian

  2019-01-04

  方法1，动态规划，最快。方法2递归有点慢，方法三递归，超级慢。在aim数值大于30的时候，三种写法，在我电脑速度快慢特别明显。用2元,3元,5元去找开100块，用递归方法，我的电脑要等到地老天荒O(∩_∩)O哈哈~ #include<iostream> #include<vector> using namespace std; int dp_solve(int *a, int n, int aim){ vector<vector<int>> dp(n, vector<int>(aim+1, 0)); for(int j = 1; j <= aim; j++){ dp[0][j] = INT_MAX; if(j >= a[0] && dp[0][j - a[0]] != INT_MAX) dp[0][j] = dp[0][j - a[0]] + 1; } for(int i = 1; i < n; i++){ for(int j = 1; j <= aim; j++) { int tmp = INT_MAX; if(j - a[i] >= 0 && dp[i][j - a[i]] != INT_MAX) tmp = dp[i][j - a[i]] + 1; dp[i][j] = min(dp[i-1][j], tmp); } } return dp[n-1][aim] == INT_MAX ? -1 : dp[n-1][aim]; } int min_res = INT_MAX; void recur_solve(int *a, int n, int aim, int k){ if(aim == 0){ min_res = min(min_res, k); return; } if(aim < 0) return; for(int i = 0; i < n; i++){ aim -= a[i]; k++; recur_solve(a, n, aim, k); aim += a[i]; k--; } } int min_res2 = INT_MAX; void recur_solve2(int *a, int n, int aim, vector<int> res){ if(aim == 0){ int size = res.size(); min_res2 = min(min_res2, size); return; } if(aim < 0) return; for(int i = 0; i < n; i++){ res.push_back(a[i]); recur_solve2(a, n, aim - a[i], res); res.pop_back(); } } int main(){ int a[] = {2,3,7}; int sum = 25; /***dp最快**/ cout << dp_solve(a, 3, sum) << endl; /***这种递归有点久**/ recur_solve(a, 3, sum, 0); cout << min_res << endl; /**这个太久了**/ vector<int> result; recur_solve2(a, 3, sum, result); cout << min_res2 << endl; return 0; }

  展开

  作者回复: 动手实验，比较不同的实现，👍

  

  4
• 
  mickey

  2019-01-04

  package Part01; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Lesson10_ex { public static void main(String[] args) { switchMoney(2, 3, 7, 100); } private static void switchMoney(int mz1, int mz2, int mz3, int total) { List<Integer[]> list = new ArrayList<Integer[]>(); int s1 = total / mz1; int s2 = total / mz2 + 1; int s3 = total / mz3 + 1; for (int i = 0; i <= s1; i++) { for (int j = 0; j <= s2; j++) { for (int k = 0; k <= s3; k++) { if (mz1 * i + mz2 * j + mz3 * k == 100) { list.add(new Integer[] { i, j, k }); } } } } Integer[] result = new Integer[3]; int min = total; for (Integer[] integers : list) { int sum = 0; for (Integer num : integers) { sum += num; } if (min > sum) { min = sum; result = integers; } } System.out.println("最小数：" + min); System.out.println(Arrays.toString(result)); } }

  展开

  

  3
• 
  罗耀龙@坐忘

  2020-04-02

  茶艺师学编程 昨天讲编辑距离，今天讲状态转移方程。 我试着这样理解，状态转移方程，就是要看到这一堆数字的“每一份”变化会给整体带来什么影响。这就好像，在自己的脑海中，模拟一遍“小树是怎么长成大树”，找到其中的“规律”。 摸到了规律，再结合给定的条件，即可寻找“最优解”。 在现实中，当一个人跟你说“我要最好的”，你可以反问TA两句，“你了解其中的规律（状态转换方程）吗？你的约束条件是什么?”

  展开

  

  2
• 
  木子皿

  2019-10-19

  动态规划的这两篇文章看了一个星期，总算是看懂了！

  作者回复: 确实不太好理解，不过一旦理解了对解题很有帮助

  共 2 条评论

  2
• 
  张洋

  2019-10-17

  答案是15 种 private static int totalNumberForMoney(int[] moneyKind,int total){ //初始化 c数组 int[] c = new int[total+1]; for(int i=1;i<c.length;i++){ c[i] = -1; } c[0] = 0; for(int i=1;i<=total;i++){ int[] data = new int[moneyKind.length]; for(int j = 0;j<moneyKind.length;j++){ if((i - moneyKind[j])<0){ data[j]= -1; continue; } data[j] = c[i - moneyKind[j]]; } int min = min(data); if(min == -1){ continue; } c[i] = min + 1; System.out.println(i + "min" + c[i]); } return c[total]; } private static int min(int[] data) { boolean flag = true; int min = -1; for(int i=0;i<data.length;i++){ if(data[i]==-1){ continue; } if(flag){ min = data[i]; flag = false; continue; } if(data[i]<min){ min = data[i]; } } return min; }

  展开

  

  2
• 
  ACHL

  2022-09-09 来自广西

  package firstPart; import java.util.Arrays; public class Lessonpratice_10_1 { /** * @Description: 使用动态规划，解决给定金额求最小纸币数问题 * @param C-给定的金额，m-给定的可能纸币 * @return int-最小纸币数 */ public static int Getres_version1(int C, int[] m) { if (C < 0) { return -1; } if (C == 0) { return 0; } int[] dp = new int[C + 1]; Arrays.fill(dp, (int)0x3f3f3f3f); dp[0] = 0; for (int i = 1; i <= C; i++) { for (int j = 0; j < m.length; j++) { if (i >= m[j]) { dp[i] = Math.min(dp[i - m[j]] + 1, dp[i]); } } } return dp[C]; } /** * @Description: 使用贪心算法，解决给定金额求最小纸币数问题 * @param C-给定的金额，m-给定的可能纸币 * @return int-最小纸币数 */ public static int Getres_version2(int C, int[] m) { if (C < 0) { return -1; } if (C == 0) { return 0; } Arrays.sort(m); int left = C; int idx = m.length - 1; int res = 0; while (true) { if (left == 0) break; int k = left / m[idx]; res += k; left -= k * m[idx]; idx--; } return res; } public static void main(String[] args) { int[] m = new int[]{2, 3, 7}; int C = 100; System.out.println(Lessonpratice_10_1.Getres_version2(0, m)); } }

  展开

  

  1
• 
  Duke

  2021-09-14

  // 作业 void Main() { // 面额已经按照大到小排序 //Console.WriteLine(Get(100, new int[] { 2, 3, 7 })); Get2(10, null); // 100 算太慢了。这种太耗资源了 Console.WriteLine($"共有【{count}】个解。"); Console.WriteLine($"最优解：{string.Join(",",result)}"); } #region 动态规划解法，也就是循环 static int Get(int total, int[] value) { if (total < 0 || value.Length < 1) return -1; int[,] c = new int[total + 1, value.Length + 1]; for (int i = 1; i <= total; i++) { var min = -1; // -1 表示无解 var str ="["; for (int j = 0; j < value.Length; j++) { if (i - c[i, j] >= 0 && i - value[j] >= 0 && c[i - value[j], value.Length] > -1) { c[i, j] = c[i - value[j], value.Length] + 1; min = c[i, j]; } else { c[i, j] = -1; } str += c[i, j] +"\t ,"; } c[i, value.Length] = min; str += min + "]"; Console.WriteLine(str); } //Console.WriteLine(c);// linqpad 可以直接打印表格形式 return c[total, value.Length]; } #endregion 动态规划解法，也就是循环 #region 递归解法 static List<int> rewards = new List<int> { 2,3,7 }; static int minLength = int.MaxValue; static int count = 0; static List<int> result = new List<int>(); static void Get2(int total, List<int> dest) { if(total < 0) return; // 无解 if(total == 0) { count++; Console.WriteLine(string.Join(",", dest)); if (dest.Count < minLength) { minLength = dest.Count; result.Clear(); dest.ForEach(i => result.Add(i)); } } if(dest == null) dest = new List<int>(); rewards.ForEach( item => { var newDest = new List<int>(); dest.ForEach(r => newDest.Add(r)); newDest.Add(item); Get2(total - item, newDest); } ); } #endregion 递归解法

  展开

  

  1
• 
  别人家的康少

  2020-12-08

  说到动态规划，你说是考虑当前子问题的最优解，我于是想到了贪心算法，请问这两者有什么区别呢

  作者回复: 动态规划虽然是当前子问题的最优解，不过由于不断的通过子问题递推到整个问题，其实是完成了对所有解的搜索，只是通过状态转移方程，缩减了很多不必要的搜索路径，是可以得到全局最优的。而贪心算法的本质决定了到达一定条件后就停止搜索，而全局最优解可能会存在于未被搜索的空间之中。简单来理解，动态规划确实搜索了所有的可能，只是在一定程度上提升了效率。而贪心可能效率更高，但是遗漏了全局最优。

  

  1
• 
  凹凸鸿

  2020-12-04

  https://www.jianshu.com/p/a617d20162cf 这篇文章写得更清楚

  作者回复: 感谢这个信息，我也来学习一下如何将这个问题说得更清楚

  

  1
• 
  zart

  2020-10-31

  public class Lesson10_2 { public static int minCoinCount(int money, ArrayList<Integer> coinArray){ if (coinArray == null || coinArray.isEmpty() || money <= 0){ return -1; } int minCoinValue = Collections.min(coinArray); if (money < minCoinValue){ return -1; } int[] c = new int[money+1]; for (int i=0; i<minCoinValue; i++){ c[i] = -1; } for (int i=minCoinValue; i<=money; i++){ ArrayList<Integer> coinNumList = new ArrayList<>(coinArray.size()); for (int coin : coinArray){ if (i == coin){ coinNumList.add(1); } else if (i-coin>0 && c[i-coin]!=-1){ coinNumList.add(c[i-coin] +1); } } c[i] = Collections.min(coinNumList); } return c[money]; } public static void main(String[] args) { ArrayList<Integer> coinArray = new ArrayList<>(3); coinArray.add(2); coinArray.add(3); coinArray.add(7); System.out.println(minCoinCount(100, coinArray)); } }

  展开

  

  1
• 
  张楠

  2020-09-21

  老师您好，我数学不是很好本课程中第二个案例（钱币组合的案例）表格中推导公式不太理解，比如：面额5 这行中2对应的c(3)+1 =2、3对应c(2) + 1 = 2，如果您有方便能给讲解下么？怎么推导出来的，谢谢

  作者回复: c(3)表示目前已经有3元，+1表示增加一个2元纸币或硬币获得总共5元，而c(2)表示目前已经有2元，+1表示增加一个3元纸币或硬币获得总共5元

  

  1