简介
动态规划是运筹学的一个分支。(管理学的重要专业基础课,利用统计学、数学模型、算法等寻找复杂问题的最佳或近似最佳的答案)
动态规划的核心是以局部最优解求全局最优解
重点
- 子问题
原问题由多个子问题组成
例如1+2+4+8
,原问题是求四个数的和,子问题是当前数+之前数的和
- 动态规划状态
即子问题可能的结果,最优解 - 边界状态值
无法用子问题概括的值,例如1+2+4+8
中第一个和第二个值,需要先1+2
之后的值才能用当前数+之前数的和
来概括 - 状态转移方程
上一个子问题解如何转换成另一个子问题的解
一、最大子序和
题目
给定一个整数数组nums
,找到一个具有最大和的连续子数组(子数组至少包含一个元素),返回其最大和。-
分析
- 子问题,以
i
个位置上的数结尾的子数组最大和,求出每个位置的最大和,最大子数组就是其中最大的值。 - 动态规划状态
i
个位置结尾的子数组最大和 - 边界状态
1
位置结尾的数组最大和 - 状态转移方程
对于每一个位置结尾的子数组,其最大值只有两种可能
第一种,上一个位置结尾的连续数组最大值+当前位置值(连续之前的数组)
第二种,当前位置的值(从新开始子数组)
求这两种操作的最大值就是当前位置结尾的连贯子数组最大值
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个台阶。
问:
有多少种方法爬到楼顶-
分析
- 子问题:原问题是到达
n
阶有多少种走法,n
阶的走法由n-1
阶台阶走法数量和n-2
阶台阶走法数量组成。因为一次只能走1
或者2
个台阶,所以第n
个台阶只能是由n-1
或者n-2
台阶走上来的,且n-1
和n-2
走上来都只有一种方法。所以子问题就是登上n-1
个台阶走法数量。 - 动态规划状态,第
i
个状态就是i
个阶梯的走法数量 - 边界值状态,第
1
和第2
阶台阶的走法 - 状态转移方程,
dp[i] = dp[i-1] + dp[i-2]
- 子问题:原问题是到达
解
- 设置递推数组 dp[n],dp[i]代表到达第
i
阶时有多少种走法 - 设置
dp[1]
和dp[2]
的值,即第一阶和第二阶的走法数量 - 利用
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];
}
}
三、打家劫舍
问题
你是一个专业的小偷,计划沿街窃取钱财。街上排列有若干房屋,相邻房屋装有相同的防盗系统,如果两个房屋都失窃会自动报警。
问:
给定一个代表存放金额的非负数数组,计算不触发报警情况下能达到最高金额-
分析
- 子问题,原问题是盗窃到最后一家或倒数第二家时能够获得的最大财宝数量。子问题就是求每个房间的最优解
- 动态规划状态,
i
个房间的状态就是该房间能获得财宝的最大值 - 边界, 第一个房间,第二个房间能获得的最大财宝
- 转移方程,
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...amount
最少硬币组合数,例如amount = 11
时最小组合就是amount = 10
、amount = 9
、amount = 6
时组合数+1中最小的。子问题就是总金额1到amount
的最优解 - 动态规划状态,
amount = i
时的最小组合数 - 边界,当硬币数额等于
amount
时dp[amount] = 1
,即一枚硬币就能组合成总金额 - 转移方程,
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];
}
}