动态规划
Table of Contents generated with DocToc (opens new window)
# 动态规划
# 概念or套路
首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。
动态规划这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！
首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。
以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
按上面的套路走，最后的结果就可以套这个框架：
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
2
3
4
5
6
7
# 1.(medium)零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1 示例 2：
输入：coins = [2], amount = 3 输出：-1 示例 3：
输入：coins = [1], amount = 0 输出：0
提示：
1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104
思路：
官方题解：
我们采用自下而上的方式进行思考。仍定义F(i)为组成金额i所需最少的硬币数量，假设在计算F(i) 之前，我们已经计算出 F(0)-F(i-1)的答案。 则F(i)对应的转移方程应为
其中 cj代表的是第j枚硬币的面值，即我们枚举最后一枚硬币面额是cj，那么需要从 i-cj这个金额的状态 F(i-cj)转移过来，再算上枚举的这枚硬币数量1的贡献，由于要硬币数量最少，所以F(i)为前面能转移过来的状态的最小值加上枚举的硬币数量1。
理解：dp[i] = min(dp[i],dp[i-coin]+1)。这里相当于最后一枚硬币面额是coin，那么amount==i的情况下，所需数量dp[i]就等于去掉这最后一枚硬币coin的情况时需要的数量，加上硬币coin的1与它本身取最小值
代码：
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp,amount+1);
dp[0] = 0;
for(int i = 1;i <= amount;i++){
for(int coin : coins){
if(i-coin<0){
continue;
}
dp[i] = Math.min(dp[i-coin]+1,dp[i]);
}
}
return dp[amount] == (amount+1) ? -1 : dp[amount];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 2.(medium)股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
思路：
我们设dp数组，dp[i]为每一天的最大利润。
思考：一天的最大利润是如何得到的呢？
即：第i天所能得到的最大利润，如果比原来的最大利润大，那么总的最大利润就是第i天能得到的最大利润；如果比原来的最大利润小，那么总的最大利润仍为[0,i-1]天里的最大利润。
第i天最大利润的计算：只要知道第[0,i-1]天之间的最小股票价格，用第i天价格减去，就能得到第i天能得到的最大利润
代码：传统利用数组，这样可以得到每一天的最大利润
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0){
return 0;
}
//设dp[i]为第i天的最大利润
//每一天的最大利润 等于max(前一天的利润,今天的股票价格-之前最小的股票价格)
//因为通过今天股票价格和之前的最小价格，我们可以计算到今天所能获得的利润有没有前面的天获得的大
int res = 0;
int min = prices[0];
for(int i=1;i<prices.length;i++){
if(prices[i]<min){
min = prices[i];
}
res = Math.max(res,prices[i]-min);
}
return res;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
不过由于题目只需要求这些天里的所有利润中的最大利润，所以可以用变量代替数组
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int min = Integer.MAX_VALUE;
for(int i=0;i<prices.length;i++){
//维护[0,i-1]区间里的最小股票
min = Math.min(min,prices[i]);
//比较最大利润与第i的最大利润取其大者
res = Math.max(res,prices[i]-min);
}
return res;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
# 3.(easy)连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
- 1 <= arr.length <= 10^5
- -100 <= arr[i] <= 100
思路1：
一开始自己想到的思路：(因为以为题目是如果和为负数，那么最大就是0)
用变量max表示要求的最大值，用curr表示[0,i-1]区间的最大值，curr每次加上nums[i]，然后更新max=Math.max(max,curr)，
如果发现此时curr<0，则将其重置为0
代码：
class Solution {
public int maxSubArray(int[] nums) {
int max = -101;
int curr = 0;
for(int i=0;i<nums.length;i++){
curr+=nums[i];
max = Math.max(curr,max);
if(curr<0){
curr = 0;
}
}
return max;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
思路2：
如果curr+nums[i]是小于nums[i]，证明前面的最大和对当前的产生负贡献，所以将cur=Math(curr+nums[i],nums[i])，然后更新max即可
状态转移方程：
代码：
class Solution {
public int maxSubArray(int[] nums) {
int max = -101;
int curr = 0;
for(int i=0;i<nums.length;i++){
curr = Math.max(curr+nums[i],nums[i]);
max = Math.max(curr,max);
}
return max;
}
}
2
3
4
5
6
7
8
9
10
11
# 4.(medium)礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入: [[1,3,1], [1,5,1], [4,2,1]] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
思路：
对于第[i,j]个位置能拿到的最大价值的礼物设为P(i,j) 由于要到[i,j]这个位置，只能从[i-1,j]和[i,j-1]两个位置出发 那么就有了P(i,j)=max{P(i-1,j), P(i,j-1)} + grid(i,j) 只要遍历整个grid得到每个位置的P(i,j)即可 注意i=0和j=0的情况
代码：
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0&&j==0){
continue;
}else if(i==0&&j!=0){
//此时只能来自上面
grid[i][j] += grid[i][j-1];
}else if(i!=0&&j==0){
//此时只能来自左边
grid[i][j] += grid[i-1][j];
}else{
grid[i][j] = Math.max(grid[i-1][j],grid[i][j-1])+grid[i][j];
}
}
}
return grid[m-1][n-1];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
还可以加一行一列，避免i或j在第一行或第一列的时候的特殊判断，代码更简洁
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
}
}
return dp[m][n];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
# 5.(medium)把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：0 <= num < 231
思路：
类似青蛙跳台阶的变种，只不过增加限制条件(
要找规律啊！！！！！)
代码：
class Solution {
public int translateNum(int num) {
String str = String.valueOf(num);
int n = str.length();
if(n<2){
return n;
}
int a = 1,b = 1,c=0;
for(int i=2;i<=n;i++){
//只有在i-1和i-2的字符能被翻译的时候 f(i)才等于f(i-1)+f(i-2)
if(str.charAt(i-2)=='1'||(str.charAt(i-1)<='5'&&str.charAt(i-2)=='2')){
c = a+b;
}else{
//否则等于f(i-1)
c = a;
}
b = a;
a = c;
}
return a;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 6.(medium)最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例 2：输入：nums = [0,1,0,3,2,3] 输出：4 示例 3：输入：nums = [7,7,7,7,7,7,7] 输出：1
思路：
首先明确是求子序列，而不是子串，子数组这种，子序列不要求连续，只要相对位置不变即可
我们设dp[nums.length]数组，dp[i]表示以nums[i]结尾的最长严格递增子序列的长度，因为以nums[i]结尾，那么子序列肯定包含nums[i]，所以我们需要将dp数组的每个值初始化为1；
因为前面的dp[i-1]-dp[0]都是以nums[i-1]~nums[0]结尾的最长严格递增子序列，所以要求dp[i]，就需要找到nums数组中0~j-1(j<i)位置有多少个小于nums[i]的nums[j]，然后就可以把nums[i]接到以这些数为结尾的最长严格递增子序列的后面，且长度加一，并更新dp[i]的值为dp[i]与dp[j]+1更新后的大值。
代码：
class Solution {
public int lengthOfLIS(int[] nums) {
//设dp[i]为以nums[i]结尾的最长严格递增子序列长度
//以nums[i]结尾,肯定包含nums[i]自己,所以将dp数组全部初始化为1
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
for(int i=0;i<nums.length;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
}
int max = 0;
for(int num:dp){
max = Math.max(max,num);
}
return max;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 7.(easy)圆圈中最后剩下的数字
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
思路：
状态转移方程：dp[i]=(dp[i−1]+m)%i
代码：
class Solution {
public int lastRemaining(int n, int m) {
int dp = 0;
for(int i=2;i<=n;i++){
dp = (dp+m)%i;
}
return dp;
}
}
2
3
4
5
6
7
8
9
# 8.(easy)最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2：
输入：nums = [1] 输出：1 示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
思路：
dp[i]表示以nums[i]结尾的和最大的连续子数组。
如果dp[i-1]小于0的，说明它对dp[i]的贡献是负的，即dp[i]不需要它，所以dp[i]=nums[i]
反之，dp[i]是需要它的，所以应该用nums[i]加上dp[i-1]
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for(int i=1;i<nums.length;i++){
// 如果dp[i-1]小于0 表示它对dp[i]的贡献是负的
// 此时dp[i]就根本不需要它，所以dp[i]直接等于nums[i]即可
if(dp[i-1]<0){
dp[i] = nums[i];
}else{
//dp[i-1]>0时它对dp[i]的贡献是正
//所以dp[i]要取得最大值应该用nums[i]来加上它
dp[i] = dp[i-1]+nums[i];
}
max = Math.max(max,dp[i]);
}
return max;
}
}
// 第i个数是必选的 而dp[i-1]是根据情况需要不选
//精简写法
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int temp = 0;
for(int num : nums){
temp = Math.max(temp+num,num);
max = Math.max(max,temp);
}
return max;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 9.(medium)乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
- 1 <= nums.length <= 2 * 10^4
- -10 <= nums[i] <= 10
- nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
思路：
常规我们想到的肯定是dp，dp[i]代表已nums[i]结尾最大的子数组的乘积，但是这里是乘积，而不是
和最大子数组，乘积在有了负数以后，会出现最大值变最小值，最小值变最大值，所以不能用求和时的dp思路。所以这里我们需要维护两个变量，
当前的最大值max
max = Math.max(max*nums[i],nums[i]);最小值，且最小值是可能为负数
minMax = Math.min(minMax*nums[i],nums[i]);在遇到当前的nums[i]是负数的时候，此次dp的结果其实是max会是最小值，minMax会是最大值，与期望不符，所以我们在计算维护max和minMax之前，将两者值交换，那么在计算维护后，max仍是最大值，minMax仍是最小值，然后再用max去维护最终结果res即可
代码：
class Solution {
public int maxProduct(int[] nums) {
//正负贡献
//dp[i]表示以nums[i]结尾的子序列的最大乘积
int res = Integer.MIN_VALUE;
//真正的大值 初始值不能是Integer.MIN_VALUE
int max = 1;
//负数的大值 初始值不能是Integer.MIN_VALUE
int minMax = 1;
for(int i=0;i<nums.length;i++){
//当有负贡献的时候 最小的就变成了最大的，最大了反而成了最小的
//这句话的理解是，当前的nums[i]<0，那么如果原来的大、小两个数都是正，那么*负数，大的会变小
//如果一正一负，乘以负数，也会导致小变大，大变小
//如果都是负数，也会导致小变大，大变小
//所以将两者交换过来，让对于nums[i]能取得大值的作为"大值"
if(nums[i] < 0){
int temp = max;
max = minMax;
minMax = temp;
}
//保证max肯定是大值
max = Math.max(max*nums[i],nums[i]);
//保证max肯定是小值
minMax = Math.min(minMax*nums[i],nums[i]);
//与大值比较记录真正结果
res = Math.max(res,max);
}
return res;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 10.(medium)打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
思路：
dp[i]表示抢第i个房屋的最大利润，分解子问题，dp[i]有两个选择，第i个抢或不抢
- nums[i]抢的时候：因为不能连续两个都抢，所以dp[i] = dp[i-2]+nums[i]
- nums[i]不抢的时候：因为不抢，所以直接抢前面的i-1个即可，所以dp[i] = dp[i-1];
然后要注意的一点是，当房子数量大于等于2时，初始化dp数组，dp[0]即为nums[0]，这个没有问题；但是dp[1]要注意，需要取nums[0]，nums[1]中的大值
代码：
class Solution {
public int rob(int[] nums) {
//dp[i]表示抢第i个房屋的最大利润
//分两种情况
//1. nums[i]抢的时候：因为不能连续两个都抢，所以dp[i] = dp[i-2]+nums[i]
//2. nums[i]不抢的时候：因为不抢，所以直接抢前面的i-1个即可，所以dp[i] = dp[i-1];
//特例情况 只有一个的时候只能抢这个 所以直接返回
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]);
}
int max = -1;
for(int rob : dp){
max = Math.max(max,rob);
}
return max;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
空间优化到O(1)
class Solution {
public int rob(int[] nums) {
if(nums.length == 1){
return nums[0];
}
//抢以前的
int robPre = nums[0];
////抢当前的
int robCurr = Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;i++){
int temp = Math.max(robPre+nums[i], robCurr);
robPre = robCurr;
robCurr = temp;
}
return robCurr;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 11.(medium)最小路径之和
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**一个机器人每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]] 输出：12
思路：
DFS：
首先想到的是dfs，但是单纯的dfs会超时，所以使用备忘录来记录
dp[i][j]对应的价值，如果memo中存在(!=0)，就不用再递归下去了，直接返回memo中的值，如果不存在，进行下面的递归。步骤：
从
grid[n-1][m-1]开始递归，dp[i][j]就等于grid[i-1][j]与grid[i][j-1]中的小值，再加上grid[i][j]，最后返回memo[i][j]即可这里要注意边界条件(base case)，当i和j都为0，即回到出发点时，即返回
grid[i][j]、当i或j小于0了，返回一个Integer的最大值，防止与有效值进行竞争。
代码：
class Solution {
int[][] memo;
public int minPathSum(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
memo = new int[n][m];
return dp(grid,n-1,m-1);
}
public int dp(int[][] grid,int i,int j){
if(i == 0 && j == 0){
return grid[0][0];
}
if(i < 0 || j < 0){
return Integer.MAX_VALUE;
}
if(memo[i][j] != 0){
return memo[i][j];
}
memo[i][j] = Math.min(dp(grid,i-1,j),dp(grid,i,j-1))+grid[i][j];
return memo[i][j];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
动态规划：
状态方程是很容易就能想到的
dp[i][j]= Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j]；但因为这是一个二维的，我们事先需要把每个
dp[i][0]和dp[0][j]求出来，即把每第一列和第一行的dp值求出来，才能继续往下面计算，所以先需要两次循环算第一行第一列
dp[i][0] = dp[i-1][0]+grid[i][0]
dp[0][i] = dp[0][i-1]+grid[0][i]剩下的工作就简单了，两重循环从(1,1)开始求
dp[i][j]即可
代码：
class Solution {
public int minPathSum(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
dp[0][0] = grid[0][0];
for(int i=1;i<n;i++){
dp[i][0] = dp[i-1][0]+grid[i][0];
}
for(int i=1;i<m;i++){
dp[0][i] = dp[0][i-1]+grid[0][i];
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[n-1][m-1];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
