简介

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

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])

• 解

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阶计算结果

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])

• 解

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数组中元素带入方程后的最小值

    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。

• 解

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