动态规划 - 归类总结_动态归类

---

动态规划(DP)思想

---

动态规划 Dynamic programming => DP

动态规划：普通递归 + dp数组记录，达到空间换时间

动态规划一般都不会很高效，因为dp[]记录了途中每个状态最优解

尽量找巧妙的方法，来做到比dp效果更好的解法

DP三大性质：

• 最优子结构
• 子问题重叠
• 无后效性（算好的dp[]不会再改）

DP四步走：

1. 拆分出子问题
2. 子问题的递推公式（状态转移方程）
3. 确定 DP 数组的计算顺序、并初始化
4. 空间优化（可选）

动态规划vs贪心算法

贪心算法是一种特殊的动态规划算法

对于一个动态规划问题，问题的最优解往往包含重复的子问题的最优解，动态规划就是为了消除重复的子问题

而贪心算法由于每一次都贪心选取一个子问题，所以不会重复计算子问题的最优解

DP问题大致分类

• 【斐波拉切】（跳台阶系列）
• 【递推型】（丑数、剪绳子、圆圈最后数）
• 【划分型】间断序列-最值（打家劫舍、股票类、不连续子序列）
• 【二维坐标型】细分为：1）棋盘dfs回溯问题（flag试错） 2）棋盘dp[][]递推问题
• 【区间型】连续序列-最值（拿石子、连续子序列）=》二维dp[][]，双指针
• 【背包型】目标值（背包（sum<=k）、和为K的序列（未必连续）、零钱兑换）
• 【树型】（树状递归、dp；经常划到树而不是动态规划）

前三类是一维dp[]，紧接后面两类是二维dp[][]，背包型可能1维、2维、多维

---

斐波拉切型

---

1. 斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n≤39

public class Solution {
   
    public int Fibonacci(int n) {
   
        int[] fi=new int[40];//设置数组记录中间结果，不然重复计算太多   //根据题目，放心设置数组大小	 
        fi[0]=0;fi[1]=1;
        for(int i=2;i<=n;i++){
   
            fi[i]=fi[i-1]+fi[i-2];
        }
        return fi[n];
    }
}
//动态规划，时间复杂度O(N),空间复杂度O(N)
//如果用递归，时间复杂度O(1.618^N)【上网查的，略小于2^N】,空间复杂度O(1)【不包括系统栈空间】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 跳台阶

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

1）斐波拉切-O(N)动态规划

public class Solution {
   
    public int JumpFloor(int target) {
   
        int frog[]=new int[100];
        frog[1]=1;frog[2]=2;
        for (int i=3;i<=target;i++){
   
            frog[i]=frog[i-1]+frog[i-2];
        }
        return frog[target];
    }
}
//原理同：斐波那契数列
//【动态规划】时间O(N)，空间O(N)
//如果只要最后的结果，那么可以撤销数组，使用a/b/c三个变量存储即可。空间复杂度减为O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2）空间O(1)的方法

public class Solution {
   
    public int jumpFloor(int target) {
   
        if(target<=2)return target;
        int lastOne = 2;  //现在位置上一个，相当于fi[i-1]
        int lastTwo = 1;  //相当于fi[i-2]
        int res = 0;
        for(int i=3; i<=target; ++i){
   
            res = lastOne + lastTwo;
            lastTwo = lastOne;
            lastOne = res;
        }
        return res;
    }
}
//这种方法的空间复杂度为：O(1)
//时间复杂度虽然也为O(N)，但是比上一种动态规划的方法耗时，因为循环里面操作较多
//相当于时间换空间，花费时间在不断倒腾地方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. 跳台阶扩展问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
1）找出公式

public class Solution {
   
    public int JumpFloorII(int target) {
   
        int way=1;for(int i=1;i<target;i++)way*=2;return way;
    }
}
//【找出数学公式】2的n-1次方：类似向n个点之间的n-1个空画横线
// 其实不难找，在找递推公式时，前几项一写就知道了
// 时间  O(N)
// 空间  O(1)
1
2
3
4
5
6
7
8
9
10
11

2）（动态规划）硬算

public class Solution {
   
    public int jumpFloorII(int target) {
   
        int[] array =new int[100];
        array[1] = 1;
        for(int i=2; i<=target; ++i){
   
            int sum = 0;
            for(int j=1; j<=i-1; ++j)sum+=array[j];
            array[i] = sum +1;  //之前所有路径，再加上直接全部的1个跳法
        }
        return array[target];
    }
}
//时间  O(N^2)
//空间  O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？
比如n=3时，23的矩形块有3种覆盖方法：

public class Solution {
   
    public int rectCover(int target) {
   
        int fi[] = new int[100];
        for(int i= 0; i<=2; ++i)fi[i]=i;
        for(int i=3; i<=target; ++i)fi[i]=fi[i-1]+fi[i-2];
        return fi[target];
    }
}
//（除了初始少许不一样，后面是斐波拉切）
// 找递推关系：分解情况==》最右边只可能为竖或横两种情况，这两种情况无交集，分别占用1个块块和2个块块
1
2
3
4
5
6
7
8
9
10
11
12

---

递推型

---

1. 丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

import java.lang.Math;

public class Solution {
   
    public int GetUglyNumber_Solution(int index) {
   
        int ugly [] = new int [2000];
        ugly[1] = 1;//第一个丑数是1  //ugly[]数组：从1开始，而不是0，增加可读性
        int t2 = 1;
        int t3 = 1;
        int t5 = 1;//标记2/3/5这三个赛道中(非独立)，潜在候选者的位置   //ugly[]下标   //t2t3t5跑得比i要慢
        for(int i=2; i<=index; ++i){
   
            ugly[i] = Math.min(Math.min(2*ugly[t2],3*ugly[t3]),5*ugly[t5]);//Java里面的min()太low了，只能两个数
            if(ugly[i] == 2*ugly[t2]) ++t2;//t2沿着主干线ugly[]走到下一个：因为这个被选中了，选下一个为候选
            if(ugly[i] == 3*ugly[t3]) ++t3;
            if(ugly[i] == 5*ugly[t5]) ++t5;//为什么要搞三个类似语句？因为：这三个可能中一个、也可能中两个、或三个全中（三个因子都含有）
        }
        return ugly[index];
    }
}
//时间 O(N)   空间 O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。（2 <= n <= 60）

方法一：数学函数求导法

【总体思路】构造函数求导，得到：m=n/e (小数的情况下)，也就是说尽量拆成一堆：2、3（最接近e的整数）

数学函数求导法：针对性规律
result= f(m) = (n/m) ^m，设n为定值，m为自变量，f(m)为乘积结果。
max{ f(m) }= max{ ln f(m) }，取对数。
求 ln f(m)= m*( ln n- ln m )最值点的m值，求导并令f(m)’=0，得到m=n/e.
e=2.718，然后因为取整数，所以是拆成一堆2、3；
具体看下：4>>>2x2；5>>>2x3；6>>>3x3 符合分析的结果。

public class Solution {
   
    public int cutRope(int target) {
   
        if(target == 2)return 1;//因为题目要求最少拆成2份
        if(target == 3)return 2;
        int res = 1;
        while(target > 4 ){
   //target剩<=4时，三种情况：4=>2*2=4; 3=>3; 2=>2; (-=3 不存在1)
            target -= 3;
            res *= 3;
        }
        return res * target;//三种情况合并处理
    }
}//时间O(N)，空间O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：动态规划

【总体思路】dp[] 存一步步的最优 + 找到 递推公式

public class Solution {
   
    int[] dp = new int[60];
    public int cutRope(int target) {
   
        if(target == 2) return 1;
        if(target == 3) return 2;//这里的策略不同，要单独拎出来
        dp[2] = 2;
        dp[3] = 3;//在target>=4的前提下，dp[]数组2~3对应的值（不必强制分两段）
        for(int i=4; i<=target; ++i){
   
            int max = Integer.MIN_VALUE;
            for(int j=2; j<=i-1; ++j){
   //果然，dp的本质是穷举
                if(max < dp[j]*(i-j)) max = dp[j]*(i-j);//动态规划重点是找到=>【最优子结构的递推公式】
            }//另一种递推：将上一行的（i-j）换成dp[i-j]
            dp[i] = max;
        }
        return dp[target];
    }
}//时间O(N^2)  空间O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 孩子们的游戏(圆圈中最后剩下的数)

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品