10 | 动态规划（下）：如何求得状态转移方程并进行编程实现？

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

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; }

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

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

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

用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.

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

方法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; }

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

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