数据结构与算法系列笔记九：动态规划

本文主要是介绍数据结构与算法系列笔记九：动态规划，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

动态规划

1、概念

动态规划：动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。

动态规划的三大步骤：

1. 定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
2. 找出数组元素之间的关系式，动态规划，有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]……dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式。而这一步，也是最难的一步。
3. 找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

2、案例

一、简单的一维DP

问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

(1)、定义数组元素的含义

按我上面的步骤说的，首先我们来定义 dp[i] 的含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法，那我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法。这样，如果我们能够算出 dp[n]，不就是我们要求的答案吗？所以第一步定义完成。

（2）、找出数组元素间的关系式

我们的目的是要求 dp[n]，动态规划的题，如你们经常听说的那样，就是把一个规模比较大的问题分成几个规模比较小的问题，然后由小的问题推导出大的问题。也就是说，dp[n] 的规模为 n，比它规模小的是 n-1, n-2, n-3…. 也就是说，dp[n] 一定会和 dp[n-1], dp[n-2]….存在某种关系的。我们要找出他们的关系。

那么问题来了，怎么找？

这个怎么找，是最核心最难的一个，我们必须回到问题本身来了，来寻找他们的关系式，dp[n] 究竟会等于什么呢？

对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式

一种是从第 n-1 级跳上来

一种是从第 n-2 级跳上来

由于我们是要算所有可能的跳法的，所以有 dp[n] = dp[n-1] + dp[n-2]。

（3）、找出初始条件

当 n = 1 时，dp[1] = dp[0] + dp[-1]，而我们是数组是不允许下标为负数的，所以对于 dp[1]，我们必须要直接给出它的数值，相当于初始值，显然，dp[1] = 1。一样，dp[0] = 0.（因为 0 个台阶，那肯定是 0 种跳法了）。于是得出初始值：dp[0] = 0.

注：分析是有问题的，因为i=2，dp[2]=2；错在对初始值的寻找不够严谨，

int f(int n){
    int[] dp = new int[n + 1];
    // 给出初始值
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    // 通过关系式来计算出 dp[n]
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    // 把最终结果返回
    return dp[n];
}

二、二维数组的DP

问题描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？（m、n值均不超过100）

还是老样子，三个步骤来解决。

步骤一、定义数组元素的含义

由于我们的目的是从左上角到右下角一共有多少种路径，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i] [j] 种路径。那么，dp[m-1] [n-1] 就是我们要的答案了。

注意，这个网格相当于一个二维数组，数组是从下标为 0 开始算起的，所以 右下角的位置是 (m-1, n - 1)，所以 dp[m-1] [n-1] 就是我们要找的答案。

步骤二：找出关系数组元素间的关系式

想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达

一种是从 (i-1, j) 这个位置走一步到达

一种是从(i, j - 1) 这个位置走一步到达

因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

步骤三、找出初始值

显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的，相当于计算机图中的最上面一行和左边一列。因此初始值如下：

dp[0] [0….n-1] = 1; // 相当于最上面一行，机器人只能一直往左走

dp[0…m-1] [0] = 1; // 相当于最左面一列，机器人只能一直往下走

  public static int calc(int m, int n) {
    if (m <= 0 || n <= 0) {
      return 0;
    }

    int[][] dp = new int[m][n];
    for(int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
      dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
      }
    }
    return dp[m-1][n-1];
  }

三、编辑距离

问题描述：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符

示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
	horse -> rorse (将 'h' 替换为 'r')
	rorse -> rose (删除 'r')
	rose -> ros (删除 'e')

解答

还是老样子，按照上面三个步骤来，并且我这里可以告诉你，90% 的字符串问题都可以用动态规划解决，并且90%是采用二维数组。

步骤一、定义数组元素的含义

由于我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为：当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]。

有时候，数组的含义并不容易找，所以还是那句话，我给你们一个套路，剩下的还得看你们去领悟。

步骤二：找出关系数组元素间的关系式

接下来我们就要找 dp[i] [j] 元素之间的关系了，比起其他题，这道题相对比较难找一点，但是，不管多难找，大部分情况下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是，从规模小的，通过一些操作，推导出规模大的。对于这道题，我们可以对 word1 进行三种操作

插入一个字符

由于我们是要让操作的次数最小，所以我们要寻找最佳操作。那么有如下关系式：

一、如果我们 word1[i] 与 word2 [j] 相等，这个时候不需要进行任何操作，显然有 dp[i] [j] = dp[i-1] [j-1]。（别忘了 dp[i] [j] 的含义哈）。

二、如果我们 word1[i] 与 word2 [j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下（注意字符串与字符的区别）：

（1）、如果把字符 word1[i] 替换成与 word2[j] 相等，则有 dp[i] [j] = dp[i-1] [j-1] + 1;

（2）、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符，则有 dp[i] [j] = dp[i] [j-1] + 1;

（3）、如果把字符 word1[i] 删除，则有 dp[i] [j] = dp[i-1] [j] + 1;

那么我们应该选择一种操作，使得 dp[i] [j] 的值最小，显然有

dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1;

于是，我们的关系式就推出来了，

步骤三、找出初始值

显然，当 dp[i] [j] 中，如果 i 或者 j 有一个为 0，那么还能使用关系式吗？答是不能的，因为这个时候把 i - 1 或者 j - 1，就变成负数了，数组就会出问题了，所以我们的初始值是计算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。这个还是非常容易计算的，因为当有一个字符串的长度为 0 时，转化为另外一个字符串，那就只能一直进行插入或者删除操作了。

public int minDistance(String word1, String word2) {
  int n1 = word1.length();
  int n2 = word2.length();
  int[][] dp = new int[n1 + 1][n2 + 1];
  // dp[0][0...n2]的初始值
  for (int j = 1; j <= n2; j++) {
    dp[0][j] = dp[0][j - 1] + 1;
  }
  // dp[0...n1][0] 的初始值
  for (int i = 1; i <= n1; i++) {
    dp[i][0] = dp[i - 1][0] + 1;
  }
  // 通过公式推出 dp[n1][n2]
  for (int i = 1; i <= n1; i++) {
    for (int j = 1; j <= n2; j++) {
      // 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1
      if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
      }
    }
  }
  return dp[n1][n2];
}

动态规划习题

来自牛客网

跳台阶

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

示例1

输入：

2

返回值：

2

复制

示例2

输入：

7

返回值：

21

解法

这是一道经典的递推题目，你可以想如果青蛙当前在第n级台阶上，那它上一步是在哪里呢？

显然，由于它可以跳1级台阶或者2级台阶，所以它上一步必定在第n-1,或者第n-2级台阶，也就是说它跳上n级台阶的跳法数是跳上n-1和跳上n-2级台阶的跳法数之和。

设跳上 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2XJP1Il9-1632038238167)(https://www.nowcoder.com/equation?tex=i&preview=true)] 级台阶有 fun(n) 种跳法，则它跳上n级的台阶有 fun(n) = fun(n-1)+fun(n-2) 种跳法。

然后，我们又思考初始的情况，跳上1级台阶只有1种跳法，跳上2级台阶有2种跳法，最终我们得到如下的递推式,这个递推式和 斐波那契比较相似。

笔试不推荐递归，可以采用斐波那契的解法二或解法三（解法二的改良）

if (target == 1 || target == 2) {
  return target;
}
int a = 1, b = 2, c = 0;
for (int i = 2; i < target; i++) {
  c = a + b;
  a = b;
  b = c;
}
return c;

public static int jumpFloor(int target) {
int a = 1, b = 1;
for (int i = 2; i <= target; i++) {
  a=a+b;
  b=a-b;
}
return a;
}

子数组的最大累加和问题

描述

给定一个数组arr，返回子数组的最大累加和

例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.

题目保证没有全为负数的数

示例1

输入：

[1, -2, 3, 5, -2, 6, -1]

返回值：

12

解法一：动态规划

  public int maxsumofSubarray(int[] arr) {
    if (arr.length == 0) {
      return 0;
    }
    int[] dp = new int[arr.length];
    dp[0] = arr[0];
    int max = dp[0];
    for (int i = 1; i < dp.length; i++) {
      dp[i] = dp[i - 1] > 0 ? dp[i - 1] + arr[i] : arr[i];
      max=Math.max(max,dp[i]);
    }
    return max;
  }

动态规划改良

  public int maxsumofSubarray(int[] arr) {
    if (arr.length == 0) {
      return 0;
    }
    int sum = arr[0];
    int max = sum;
    for (int i = 1; i < arr.length; i++) {
      sum = sum > 0 ? sum + arr[i] : arr[i];
      max = Math.max(max, sum);
    }
    return max;
  }

买卖股票的最好时机

描述

假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。

示例1

输入：

[1,4,2]

返回值：

3

示例2

输入：

[2,4,1]

返回值：

2

解法一：动态规划

dp[i]表示前i日的最大利润。

则转移方程为：
dp[i] = max( dp[i-1], prices[i] - min(prices[0 -> i]))。

也就是说，每日的最大利润为以下两项的大者：

• 昨天的最大利润
• 在当天以前的某个股价最低的一天买入股票，并在当天卖出股票，以此赚取的利润

初始：
dp[0] = 0;

返回值：
dp[prices.length - 1]

public static int maxProfit(int[] prices) {
  if (prices.length == 0) {
    return 0;
  }
  int maxPro = 0;
  int min = prices[0];
  for (int i = 1; i < prices.length; i++) {
    maxPro = Math.max(maxPro, prices[i] - min);
    min = Math.min(min, prices[i]);
  }
  return maxPro;
}

解法二：动态规划改良（双指针）

用两个指针，一个指针记录访问过的最小值（注意这里是访问过的最小值），一个指针一直往后走，然后计算他们的差值，保存最大的即可

public static int maxProfit(int[] prices) {
  if (prices.length == 0) {
    return 0;
  }
  int min = prices[0];
  int maxPro = 0;
  for (int i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    maxPro = Math.max(prices[i] - min, maxPro);
  }
  return maxPro;
}

换钱的最小货币数

描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

【要求】

时间复杂度O(n \times aim)O(n×aim)，空间复杂度On。

示例1

输入：

[5,2,3],20

返回值：

4

示例2

输入：

[5,2,3],0

返回值：

0

示例3

输入：

[3,5],2

返回值：

-1

备注

0≤n≤1000
0≤aim≤5000

解法：动态规划

public static int minMoney(int[] arr, int aim) {
  int max = aim + 1;  //定义一个全局变量
  int[] dp = new int[aim + 1];  //dp[i]的含义是目标值为i的时候最少钱币数是多少
  Arrays.fill(dp, max);  //把dp数组全部定义为最大值
  dp[0] = 0;
  for (int i = 0; i <= aim; i++) {  //遍历目标值
    for (int j = 0; j < arr.length; j++) {  //遍历钱币
      if (arr[j] <= i) {  //如果当前钱币比目标值小就可以兑换
        dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
      }
    }
  }
  return dp[aim] > aim ? -1 : dp[aim];
}

背包问题

描述

已知一个背包最多能容纳物体的体积为 V

现有 N 个物品，第 i 个物品的体积为Vi, 重量为 Wi

求当前背包最多能装多大重量的物品?

数据范围：

示例1

输入：

10,2,[[1,3],[10,4]]

返回值：

4

说明：

第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4   

解法：动态规划

面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。

**解决办法：**声明一个大小为 dp[n][V] 的二维数组， dp[i][j] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出dp[i][j] 的计算方法
（1） j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿 dp[ i ][ j ] = dp[ i-1 ][ j ]
（2） j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。

• 如果拿取，dp[ i ][ j ]=dp[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的dp[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。
• 如果不拿，dp[ i ][ j ] = dp[ i-1 ][ j ] , 同（1）

究竟是拿还是不拿，自然是比较这两种情况那种价值最大。

由此可以得到状态转移方程

if(j>=w[i])
    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else
    dp[i][j]=dp[i-1][j];

根据题意修改得到：

public static int knapsack(int V, int n, int[][] vw) {
  if (V == 0 || n == 0 || vw == null) {
    return 0;
  }
  int[][] dp = new int[n + 1][V + 1];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= V; j++) {
      if (j < vw[i - 1][0]) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
      }
    }
  }
  return dp[n][V];
}

最长无重复子数组

描述

给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

示例1

输入：

[2,3,4,5]

返回值：

4

说明：

[2,3,4,5]是最长子数组    

示例2

输入：

[2,2,3,4,3]

返回值：

3

说明：

[2,3,4]是最长子数组    

示例3

输入：

[9]

返回值：

1

示例4

输入：

[1,2,3,1,2,3,2,2]

返回值：

3

说明：

最长子数组为[1,2,3]   

示例5

输入：

[2,2,3,4,8,99,3]

返回值：

5

说明：

最长子数组为[2,3,4,8,99] 

解法一： 双指针+回头遍历（ 动态规划改良）

  public static int maxLength1(int[] arr) {
    int tmp = 0, res = 0;
    for (int right = 0; right < arr.length; right++) {
      int left = right - 1;
      while (left >= 0 && arr[left] != arr[right]) {
        left--;
      }
      tmp = tmp < right - left ? tmp + 1 : right - left;
      res = Math.max(res, tmp);
    }
    return res;
  }

• 时间： O(n*n)
• 空间： O(1)

解法二： 滑动窗口

public static int maxLength(int[] arr) {
  if (arr.length < 2) {
    return arr.length;
  }
  HashMap<Integer, Integer> map = new HashMap<>();
  int res = 0;
  int left = -1;
  for (int right = 0; right < arr.length; right++) {
    if (map.containsKey(arr[right])) {
      left = Math.max(left, map.get(arr[right]));
    }
    res = Math.max(res, right - left);
    map.put(arr[right], right);
  }
  return res;
}

• 时间： O(n) n为数组的长度
• 空间：O(n) n为HashMap的长度。

最长公共子串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

示例1

输入：

"1AB2345CD","12345EF"

返回值：

"2345"

解法：动态规划

对于字符串str1（长度为m）和str2(长度为n)，我们可以使用一个二维整形数组(m * n)实现动态规划算法。

思路：
dp[i][j]：表示在str1中以坐标i结尾的子串与str2中以坐标j结尾的子串，最长公共子串的长度（从i，j的位置往前推）

递推方程：

• 如果str1第i个字符不等于str2第j个字符，那么dp[i][j] = 0
• 否则 dp[i][j] = dp[i-1]d[j-1] + 1

关于字符串的截取：
使用一个整型变量maxLength来记录当前的最长公共子串的长度
使用一个整型变量lastIndex来指向str1中当前最长公共子串的最后一个字符的下标

public static String LCS(String str1, String str2) {
  int m = str1.length();
  int n = str2.length();
  int[][] dp = new int[m][n];
  int maxLength = 0;
  int lastIndex = 0;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (str1.charAt(i) == str2.charAt(j)) {
        if (i == 0 || j == 0) {
          dp[i][j] = 1;
        } else {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          lastIndex = i;
        }
      }
    }
  }
  return str1.substring(lastIndex - maxLength + 1, lastIndex + 1);
}

这篇关于数据结构与算法系列笔记九：动态规划的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！