JAVA蓝桥杯备考—6.动态规划(一)

1.线性DP

动态规划简称 DP，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。
动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

动态规划的几个步骤
1.即划分子问题
2.状态表示。一般用数组dp[i]表示当前状态
3.状态转移，即当前状态是由前面那些状态转移过来的 例如 dp[i]=dpli-1],表示当前状态可以由上一个状态转移过来
4.确定边界，确定初始状态

线性DP是动态规划问题中的一类问题，指状态之间有线性关系的动态规划问题。
所谓线性DP，就是递推方程是有一个明显的线性关系的，一维线性和二维线性都有可能。
而我们在求的时候，有一个明显的求的顺序:即一行一行地来求。这样的有线性顺序的叫做线性DP

1.取钱 – 蓝桥云课 (lanqiao.cn)

/*
黄开的银行最近又发行了一种新面额的钞票面值为 4，所以现在黄
有5种面额的钞票，分别是 20.10.5.4.1但是不变的是他小
气，现在又有很多人来取钱，黄又不开心了，请你算出每个来取钱
的人黄应该给他至少多少张钞票
*/
import java.util.Arrays;
import java.util.Scanner;

public class 取钱 {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int[] arr = { 1, 4, 5, 10, 20 };
        int[] dp = new int[10001]; // 索引为金额, 值为方案数
        Arrays.fill(dp, 10000);
        dp[0] = 0; // 0金额的可选方案数量为0个
        for (int i = 1; i < dp.length; ++i) { // 枚举子问题金额数
            for (int j : arr) { // 每个子问题可选方案
                if (i >= j) { // 当金额大于等于面额时
                    dp[i] = Math.min(dp[i - j] + 1, dp[i]); // 选择当前面额后 +1，且寻找剩余金额时方案数累加，与当前j之后的面额继续对比方案数
                }
            }
        }
        while (sc.hasNext()) {
            System.out.println(dp[sc.nextInt()]);
        }
    }

}

2.破损的楼梯 – 蓝桥云课 (lanqiao.cn)

小蓝来到了一座高耸的楼梯前，楼梯共有N级台阶，从第0级台
阶出发。小蓝每次可以迈上1级或2级台阶。但是，楼梯上的第
a1级、第a2级第a3级，以此类推，共 M 级台阶的台阶面已经
坏了，不能踩上去。
现在，小蓝想要到达楼梯的顶端，也就是第N级台阶，但他不能
踩到坏了的台阶上。请问他有多少种不踩坏了的台阶到达顶端的方
案数?
由于方案数很大，请输出其对10^9+7取模的结果

2.二维DP 

 状态都只有一个维度，一般为dpli]，称之为线性动态规划。
当维度有两个的时候，需要用二维的状态来解决问题，例如棋盘、矩阵、路径等类别的问题
更准确的说，二维动态规划指线性动态规划的拓展，在一个平面上做动态规划。

//题目大意:对于n*m的矩阵，每个点只能往下或者往右，计算从0,0点走到n-1,m-1点一共有多少种路径
解析: 我们定义dp数组 dp[i][j]为到达第i行，第j列的路径数。因为只能向下和右走推出状态转移方程为
dp[i][j]=dp[i-1][j]+dp[i][j-1]。dp数组初始状态为dp[0][0]=1,表示起点有一种方案。

1.传球游戏 – 蓝桥云课 (lanqiao.cn) 

1.摆花 – 蓝桥云课 (lanqiao.cn)

3.LIS

最长上升子序列，简称LIS。假设我们有一个序列bi，当b1<b2<..<bs的时候，我们称这个序列是上
升的。
对于给定的一个序列(a1,a2,.. aN)，我们也可以从中得到一些上升的子序列(ai1, ai2,.., aik)，这里1<=i1<i2<…<ik<= N，但必须按照从前到后的顺序。比如，对于序列(1,7,3,5,9,4,8)，我们就会得到一些上升的子序列，如(1,7,9),(3,4,8),(1,3,5,8)等等，而这些子序列中最长的(如子序列(1,3,5,8))，它的长度为4，因此该序列的最长上升子序列长度为4。
这是一个经典dp问题。子序列指的是数组中不一定连续但先后顺序一致的n个数组。
在求解LIS问题中，我们一般定义dp[i]表示以索引i结尾的最长子序列长度。
可以退出状态转移方程为
if(dp[i]>dp[j])dp[i]=Math.max(dp[j]+1,dp[i]);(0<=j<i)
else dp[i]=Math.max(1,dp[i]);
时间复杂度为(n2)

1.蓝桥勇士 – 蓝桥云课 (lanqiao.cn)

4.LCS

LCS (最长公共子序列) 是一个经典的DP模型。
这节课我们讲解O(n^2)时间复杂度的LCS模型。
LCS问题是给定两个序列A和B，求它们的最长公共子序列。
在求解LCS时，一般我们会设dp[i][j]表示A [1~i]序列和B[1~j]序列中 (不规定结尾) 的最长
公共子序列的长度，状态转移方程为:
if a[i]=b[j];dp[i][j] = dp[i-1][j-1]+1
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
解释一下:当a[i]=b[j]时，可以将他们作为插入到LCS的后面，使得长度变长1，当a[i]!=b[j]
时，说明此时LCS不会延长，那就要从dp[i-1][j]和dp[i][j-1]中取大的作为最长的长度。

1.最长公共子序列 – 蓝桥云课 (lanqiao.cn)