0%

动态规划

发表于 分类于

文章字数：1887,阅读全文大约需要7分钟

简介

动态规划是运筹学的一个分支。（管理学的重要专业基础课，利用统计学、数学模型、算法等寻找复杂问题的最佳或近似最佳的答案）
动态规划的核心是以局部最优解求全局最优解
重点

  1. 子问题
    原问题由多个子问题组成
    例如 1+2+4+8，原问题是求四个数的和，子问题是当前数+之前数的和
  2. 动态规划状态
    即子问题可能的结果，最优解
  3. 边界状态值
    无法用子问题概括的值，例如 1+2+4+8中第一个和第二个值，需要先1+2之后的值才能用当前数+之前数的和来概括
  4. 状态转移方程
    上一个子问题解如何转换成另一个子问题的解

一、最大子序和

  • 题目
    给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。

  • 分析

    1. 子问题，以i个位置上的数结尾的子数组最大和，求出每个位置的最大和，最大子数组就是其中最大的值。
    2. 动态规划状态
      i个位置结尾的子数组最大和
    3. 边界状态
      1位置结尾的数组最大和
    4. 状态转移方程
      对于每一个位置结尾的子数组，其最大值只有两种可能
      第一种，上一个位置结尾的连续数组最大值+当前位置值（连续之前的数组）
      第二种，当前位置的值（从新开始子数组）
      求这两种操作的最大值就是当前位置结尾的连贯子数组最大值
      dp[i] = max(dp[i - 1] + num[i], mun[i])

  • 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        }
        int max = dp[0];
        for (int i : dp) {
            max = Math.max(i, max);
        }
        return max;
    }
}

二、爬楼梯

  • 题目
    假设你在爬楼梯，需要n(整数)阶才能到达楼顶。
    每次可以爬1或者2个台阶。
    问：
    有多少种方法爬到楼顶

  • 分析

    1. 子问题：原问题是到达n阶有多少种走法，n阶的走法由n-1阶台阶走法数量和n-2阶台阶走法数量组成。因为一次只能走1或者2个台阶，所以第n个台阶只能是由n-1或者n-2台阶走上来的，且n-1和n-2走上来都只有一种方法。所以子问题就是登上n-1个台阶走法数量。
    2. 动态规划状态，第i个状态就是i个阶梯的走法数量
    3. 边界值状态，第1和第2阶台阶的走法
    4. 状态转移方程，dp[i] = dp[i-1] + dp[i-2]

  • 解

  1. 设置递推数组 dp[n]，dp[i]代表到达第i阶时有多少种走法
  2. 设置dp[1]和dp[2]的值，即第一阶和第二阶的走法数量
  3. 利用i循环递推，从3到n阶计算结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int climbStairs(int n) {
        if(n == 1) {
            return 1;
        }
        if(n == 2) {
            return 2;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for(int i=2; i<n ;i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n - 1];
    }
}

三、打家劫舍

  • 问题
    你是一个专业的小偷，计划沿街窃取钱财。街上排列有若干房屋，相邻房屋装有相同的防盗系统，如果两个房屋都失窃会自动报警。
    问：
    给定一个代表存放金额的非负数数组，计算不触发报警情况下能达到最高金额

  • 分析

    1. 子问题，原问题是盗窃到最后一家或倒数第二家时能够获得的最大财宝数量。子问题就是求每个房间的最优解
    2. 动态规划状态，i个房间的状态就是该房间能获得财宝的最大值
    3. 边界， 第一个房间，第二个房间能获得的最大财宝
    4. 转移方程，i个房间最大值有两种可能，一种是选择当前房间，另一种是不选择当前房间
      选择：不能盗窃相邻房间，所以值为i-2间房最大值+当前房间财宝值
      不选择：上一间的最大值
      再挑选选择和不选择中的最大值就是当前房间的最大值
      dp[i] = max(dp[i-2] + num[i], dp[i-1])

  • 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(int[] nums) {
        // 边界情况
        if (nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }
}

四、零钱兑换

  • 题目
    给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
    coins[1, 2, 5], amount = 11

  • 分析

    1. 子问题，1...amount最少硬币组合数，例如amount = 11时最小组合就是amount = 10、amount = 9、amount = 6时组合数+1中最小的。子问题就是总金额1到amount的最优解
    2. 动态规划状态， amount = i时的最小组合数
    3. 边界，当硬币数额等于amount时dp[amount] = 1,即一枚硬币就能组合成总金额
    4. 转移方程，min(dp[i] = dp[i-coin])，coins数组中元素带入方程后的最小值
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      public static int coinChange(int[] coins, int amount) {
          if (amount == 0) {
              return 0;
          }
          int[] dp = new int[amount + 1];
          int coinsMin = coins[0];
          for (int i : coins) {
              if (i <= amount) {
                  dp[i] = 1;
                  coinsMin = Math.min(coinsMin, i);
              }
          }
          for (int i = coinsMin * 2; i <= amount; i++) {
              for (int j : coins) {
                  if (i - j > 0 && i - j <= amount && dp[i - j] > 0) {
                      if (dp[i] == 0) {
                          dp[i] = dp[i - j] + 1;
                      } else {
                          dp[i] = Math.min(dp[i], dp[i - j] + 1);
                      }
                  }
              }
          }
          return dp[amount] == 0 ? -1 : dp[amount];
      }

五、地下城游戏

  • 题目
    一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
    骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
    有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
    为了尽快到达公主，骑士决定每次只向右或向下移动一步。

  • 分析
    看到题目首先想到的是从 dungeon[0][0]开始，计算向右或向下过程中扣除或增加的总血量，但是制定转移方程的时候却有个问题，判断向右或是向下的时候需要考虑两个变量，一个是总血量，另一个是最低血量。需要在追求总血量最小的时候保证路径中任意一格时血量都在0之上。
    看了官方解答，正确的解法是从dungeon[m - 1][n - 1]也就是公主所在处规划。计算每个格子达到终点需要多少初始值，则有转移方程dp[i][j] = min(1 - dp[i - 1][j], dp[i][j - 1])。意为从下一步需要的初始值推算当前需要的初始值。又因为初始值必须大于1，所以调整一下转移方程dp[i][j] = max(1, min(1 - dp[i - 1][j], dp[i][j - 1])),使其小于1则初始值为1。

  • 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length;
        int m = dungeon[0].length;
        int[][] dp = new int[n][m];
        dp[n - 1][m - 1] = Math.max((1 - dungeon[n - 1][m - 1]), 1);
        for (int i = m - 2; i >= 0; i--) {
            dp[n - 1][i] = Math.max(dp[n - 1][i + 1] - dungeon[n - 1][i], 1);
        }
        // 只有一行的情况下，直接返回
        if (dungeon.length == 1) {
            return dp[0][0];
        }
        for (int i = n - 2; i >= 0; i--) {
            dp[i][m - 1] = Math.max(dp[i + 1][m - 1] - dungeon[i][m - 1], 1);
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = m - 2; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j] - dungeon[i][j], dp[i][j + 1] - dungeon[i][j]));
            }
        }
        return dp[0][0];
    }
}