程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23346 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

10 | 动态规划(下):如何求得状态转移方程并进行编程实现?

黄申 2019-01-04
你好,我是黄申。
上一节,我从查询推荐的业务需求出发,介绍了编辑距离的概念,今天我们要基于此,来获得状态转移方程,然后才能进行实际的编码实现。

状态转移方程和编程实现

上一节我讲到了使用状态转移表来展示各个子串之间的关系,以及编辑距离的推导。不过,我没有完成那张表格。现在我把它补全,你可以和我的结果对照一下。
这里面求最小值的 min 函数里有三个参数,分别对应我们上节讲的三种情况的编辑距离,分别是:替换、插入和删除字符。在表格的右下角我标出了两个字符串的编辑距离 1。
概念和分析过程你都理解了,作为程序员,最终还是要落脚在编码上,我这里带你做些编码前的准备工作。
我们假设字符数组 A[] 和 B[] 分别表示字符串 A 和 B,A[i] 表示字符串 A 中第 i 个位置的字符,B[i] 表示字符串 B 中第 i 个位置的字符。二维数组 d[,] 表示刚刚用于推导的二维表格,而 d[i,j] 表示这张表格中第 i 行、第 j 列求得的最终编辑距离。函数 r(i, j) 表示替换时产生的编辑距离。如果 A[i] 和 B[j] 相同,函数的返回值为 0,否则返回值为 1。
有了这些定义,下面我们用迭代来表达上述的推导过程。
如果 i 为 0,且 j 也为 0,那么 d[i, j] 为 0。
如果 i 为 0,且 j 大于 0,那么 d[i, j] 为 j。
如果 i 大于 0,且 j 为 0,那么 d[i, j] 为 i。
如果 i 大于 0,且 j 大于 0,那么 d[i, j]=min(d[i-1, j] + 1, d[i, j-1] + 1, d[i-1, j-1] + r(i, j))。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(62)

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

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

    2019-01-31
    9
  • Joe
    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;
    }

    作者回复: 答案正确 👍

    2019-01-14
    6
  • 冰木
    老大,我可能没有得到要领,可以推到下,表格中,第一行,第二列吗?

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

    2019-01-26
    5
  • 阿信
    编辑距离,刚开始没看太明白。后台看了下其他的博客,结合一起进行理解。表格里面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)这个位置时的距离。

    我是先看懂了后面的推导公式,再看明白编辑推导表格。
    2019-06-11
    3
  • 我心留
    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

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

    2019-01-05
    3
  • lianlian
    方法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;
    }

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

    2019-01-04
    3
  • caohuan
    本篇所得: 1.求解 最值可用动态规划 方法;
    2.状态转移 可以把 大问题 分解为 小问题,再分解为 可以处理的问题,即 把 不可以处理的问题 分解为可以 处理的小问题( 也为子问题);
    3.动态规划 适用于 下一个 状态与上一个状态有固定关系;
    4.搜索引擎的 搜索词的查询推荐, 英文可用 编辑距离,中文 需要 转化 比 如转为英文 再使用 编辑距离;
    5.从问题开始 ,初步分解 大问题为可解的子问题 为动态规划的方法,由问题 推到答案,也为反向思维法。

    回答老师的问题:固定金额,找最小钱币数量,可用倒推法,总金额 减去 最大的 钱币数额 ,然后从钱币中寻找该数额,没有 再把该数额逐渐减去 大的数额,一步步分解,可得 钱币的数量,该方法是 动态规划,但不能保证寻找的是最小的数量,局部最优 不一定全局最优,如果 需要寻找全部最优 需要运用 排列和组合。
    2019-01-21
    2
  • mickey
    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));
    }
    }
    2019-01-04
    2
  • 梅坊帝卿
    按照面值排序优先取最大的方法 不一定能取到解 除非有万能的面额1 比如 2 5 7 总数15

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

    2019-01-04
    2
  • Vincent🌫
    2x+3Y+7Z = 100(100 表示total)
    X+Y+Z = min
    这个是3元一次方程,但是只有两条公式,会有无数解,最优解只有一个
    2019-11-19
    1
  • Geek_zy
    答案是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;
        }
    2019-10-17
    1
  • 予悠悠
    用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.

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

    2019-01-22
    1
  • xiaobang
    min的三个参数应该分别是插入删除替换,或者插入插入替换吧

    作者回复: 是的

    2019-01-15
    1
  • somenzz
    https://github.com/somenzz/geekbang/blob/master/mathOfProgramer/chapter10_dynamic_programming.py
    实现了循环和递归,循环的方式快,递归的方式特别慢。
    个人感觉递归是从后往前推导的,每一步的结果不论是否最优都保存在堆栈中,都占用了内存空间,算法上已经不属于动态规划。

    循环的方式不论 num 有多大,仅占用了7个变量的内存空间,每一步都保留上一步的最优解,因此效率较高,而且可以方便地打印出有最小数量的组合。

    循环方式的代码的输出如下:
     1 -> None
     2 -> (1, [2])
     3 -> (1, [3])
     4 -> (2, [2, 2])
     5 -> (2, [2, 3])
     6 -> (2, [3, 3])
     7 -> (1, [7])
     8 -> (3, [2, 3, 3])
     9 -> (2, [2, 7])
     10 -> (2, [3, 7])
     100 -> (15, [2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7])


    作者回复: 确实,动态规划使用循环更快

    2019-01-07
    1
  • 菩提
    思考题编码:
    public static int least_count(int num) {
    if (num < 0)
    return -1;
    int len = num;
    if (num < 9)
    len = 8;
    int[] c = new int[len + 1];
    c[0] = -1;
    c[1] = -1;
    c[2] = 1;
    c[3] = 1;
    c[4] = 2;
    c[5] = 2;
    c[6] = 2;
    c[7] = 1;
    c[8] = 3;

    if (num < 9) {
    return c[num];
    }

    for (int i = 9; i <= num; i++) {
    int a = c[i - 2] + 1;
    int b = c[i - 3] + 1;
    int min = Math.min(a, b);
    int m = c[i - 7] + 1;
    min = Math.min(min, m);
    c[i] = min;
    }

    return c[num];
    }

    public static void main(String[] args) {
    System.out.println(least_count(100));
    }

    运行结果: 15

    作者回复: 思路正确👍,编码可以稍微再通用点,用循环访问不同的币值

    2019-01-06
    1
  • Feng.X
    递归的写法:
    这里举例了凑成11元的最少币数
    import java.util.*;

    public class MinCoins {
    public static int[] arr={7,3,2};
    public static int minNum=Integer.MAX_VALUE;
    public static HashMap<Integer,Integer> min_map=new HashMap<Integer,Integer>();
        public static void main(String []args) {
            System.out.println("Coins:"+Arrays.toString(arr));
    minCoins(0,11,new HashMap<Integer,Integer>());
    System.out.println("MinCoins:");
    for (Map.Entry<Integer,Integer>entry:min_map.entrySet()){
    System.out.println(entry.getKey()+":"+entry.getValue());
    }
        }

    public static void minCoins(int index,int aim,HashMap<Integer,Integer> map){
    if(index==arr.length||aim==0){
    if(aim==0){
    int num=0;
    for (Integer value:map.values())
    num+=value;
    if(num<minNum) min_map=map;
    }
    return;
    }
    for(int i=0;arr[index]*i<=aim;i++){
    HashMap<Integer,Integer> new_map=(HashMap<Integer,Integer>)map.clone();
    new_map.put(arr[index],i);
    minCoins(index+1,aim-arr[index]*i,new_map);
    }
    }
    }
    2019-01-04
    1
    1
  • lianlian
    老师早上好( ^_^)/,在第一题求r的时候,条件判断语句应该是a.charAt(i+1) != b.charAt(j+1)吧😄 ?

    作者回复: 应该是i和j没错,只是这里的i和j对应于d[i+1][j+1]。这里比较容易让人混淆,主要是因为d中的0下表表示的是空串,而不是字符串中的第一个字符。我之后将代码注释加一下

    2019-01-04
    1
  • teddytyy
    int coin change(int[] coins, int coinNum, int account) {
    vector<int> dp = vector<int>(account+1, account+1);
    dp[0] = 0;
    for (int i = 1; i<=account;i++) {
    for (int j=0; j<coinNum; j++) {
    if(i-coins[j] >=0) dp[i]= min(dp[i-coins[j]], dp[i]);
    }
    }
    return dp[account] != account+1 ? dp[account] : -1;
    }
    2019-12-05
  • 脱缰的野马
    老师你好状态转移表中第二行第二列的数字组合是(2,2,0)吧?为啥是(2,3,0)呢

    作者回复: 这里确实是个笔误

    2019-12-03
  • ricardo
    js循环 重点是判断条件,将所有的不可能的组合事先规避掉,counts取值为0,在的判断最小counts的时候去除为0的值,再取最小值


           function countMin(total, currency) {
            let totalArr = new Array(total+1).fill(0);
            let tempCounts = new Array(currency.length).fill(0);
            for (let i=1; i < totalArr.length; i++) {
              for (let j=0; j < currency.length; j++) {
                if(i - currency[j] >= 0) {
                  // 总额大于当前钱币的面值的情况下,去修改 对应的钱币的数量,因为是从小到大,所以肯定数量会从1开始
                  tempCounts[j] =
                  (i - currency[j] === 0 || i - currency[j] >= Math.min(...currency))
                  ? totalArr[i - currency[j]] + 1 : 0;
                  // 为什么每次都+1呢, totalArr[i - currency[j]]代表的是上一个金额总和所需钱币的数量,+当前面值 (1张)
                }
              }
              // 在tempCounts中0的组合是不存在的,比大小的时候要排除掉
              // 排除了0的干扰 但是还存在 totalArr[8 - 7] 这样的不符合常理的组合
              let filterTotalArr = tempCounts.filter(x=> x!==0 );
              if(filterTotalArr.length <= 0){
                totalArr[i] = 0;
              }else {
                totalArr[i] = Math.min(...filterTotalArr);
              }
             
                console.log('----', tempCounts, tempCounts.filter(x=> x!==0 ), totalArr[i], i );
          }



          // 这里为什么要+1呢, 上面的i总是比 total小1,这个答案好像不怎么合理,因为你把totalArr 初始化为ew Array(total+1).fill(0);后结果不对
          //
          return totalArr[totalArr.length - 1]
        }

    2019-11-28
收起评论
62
返回
顶部