蓝桥杯算法 - DP

上一篇：[[蓝桥杯算法-排序、递归、全排列]]

动态规划（dp）

dp即动态规划，常用于：数学，计算机科学，管理学，经济和生物信息学。
dp在生活中也很常见，如：你今天有很多任务，你从中需要找到一种最优的方式去解决，这就是dp。

什么是dp

dp就是一种分为治之的思想，通过将一个大的问题分解成为一个个小问题，然后通过求得小问题的解来最终解决这个大的问题。
特征：

分解问题
解决子问题
组合子问题的解
避免重复

核心思想：

拆分子问题
记住过程
避免重复运算

例子：

1+1+1+1+1+1 = ？ 6
如果在左边直接+1 ，那么结果是多少？
因为之前已经得到了结果。所以能够根据结果直接+1得到答案。

自顶而下求解递归经典例题（青蛙跳台阶）

一只青蛙，一次可以跳上1级台阶，一次也可以跳上2级台阶。求跳上10级台阶，共有多少种跳法。

思路分析：

要跳上第10层台阶，可以从第9层跳一个台阶或者从第8层跳2个台阶。
要跳上第9层台阶，可以从第8层跳一个台阶或者从第7层跳2个台阶
·······

假设跳上第n级台阶的跳法是f(n)，那么：

f(10) = f(9)+f(8)
f(9) = f(8)+f(7)
···
f(2) = 2 //2种跳法
f(1) = 1

上述过程为拆分子问题的过程，将跳上第10层的方法 = 跳上第9层+跳上第8层

代码思路：

使用递归求解
结束条件是等于1或者等于2的时候返回1 或者2
递归函数是 Fn(n-1)+Fn(n-2)；即返回条件

代码如下：

package test01;
public class Main_P19 {
	public static void main(String[] args) {
		int result = jump(10);
		System.out.println("所有跳法一共有："+result+"种");
	}
	public static int jump(int n) {
		if(n == 1) {
			return 1;
		}
		if(n == 2) {
			return 2;
		}
		return jump(n-1)+jump(n-2);   //例如第10层台阶就有 从第九层跳一个台阶和从第8层跳2个台阶  这两种方法的和
	}
}

dp如何改进

使用字典：上述题目是使用递归来解决的，那么不可避免会出现运行时间长的问题。那么如何解决的呢？那就是使用字典来存储运行结果[[蓝桥杯算法-排序、递归、全排列#^fc4363]] 。
上述使用字典就对应了dp中的“记住过程”这个核心思想。（使用数组和map（键值对））

青蛙跳台阶优化

优化思路：

使用字典来进行优化算法运行时间
使用map字典

代码如下：

public static void main(String[] args) {
		HashMap<Integer, Integer> map = new HashMap<>(); //定义map来存储递归的结果
		long l1 =  System.currentTimeMillis();
		int result = jump(40,map);
		long l2 =  System.currentTimeMillis();
		System.out.println("所有跳法一共有："+result+"种");
		System.out.println(l2-l1);
	}
	public static int jump(int n ,HashMap<Integer, Integer> map) {
		//如果包含为n的键，则返回值
		if(map.containsKey(n)) {
			return map.get(n);
		}else {
			
		}
		if(n == 1) {
			return 1;
		}
		if(n == 2) {
			return 2;
		}
		//例如第10层台阶就有 从第九层跳一个台阶和从第8层跳2个台阶  这两种方法的和
		int result =  jump(n-1,map)+jump(n-2,map);   //用result来存储值
		//将值添加到map
		map.put(n, result);
		return result;
	}

因为动态规划就是将问题拆分成为子问题，那个原来这个大的问题的时间复杂度=小问题花费的时间×小问题的个数

这个的字典可以选择map，list，数组等来存贮。

动态规划和递归

动态规划和递归有区别，但是解题方法类似：

递归是自上而下的：从f（10） -> f (1)
动态规划是自下而上的：从 f(1) -> f(10)

动态规划dp解题步骤

最优子结构：如 f（10） = f（9）+ f(8) 那么 9和8就是最优子结构，就是构成f10的最简化的结构
状态转移方程：原问题和拆分问题的转化关系，用一个方程表示：f10 = f9+f8
边界：我认为就是结束条件。如f1 = 1 和 f2 = 2 就是结束条件。到次时候递归结束。动态规划运算也结束。
重叠子：运算中出现的重叠部分。如 f10 = f9+f8 f9 = f8 + f7 在这部分运算当中重叠子就是 f8

优化：在这里插入图片描述

使用for循环来解决了问题

代码如下：

public class Main_P21 {
	public static void main(String[] args) {
		System.out.println(ways(10));
	}
	public static int ways(int n) {
		if(n == 1) {
			return 1;
		}
		if(n ==2 ) {
			return 2;
		}
		int a = 1, b = 2, temp = 0;
		for (int i = 3; i <= n; i++) {
			temp = a+b;
			a = b;
			b = temp;
		}
		return temp;
	}
}

动态规划的解题思路

什么样的问题适合动态规划？

如果一个问题能够把所有答案穷举出来，并且存在重叠子，那么它适合用动态规划来解决。

动态规划的经典应用场景：

最长增长子序列
最小（大）距离
背包问题
凑零钱问题
等等

动态规划的解题思路：

核心思想：拆分子问题，记住过程，减少重叠子运算。
穷举分析：就是把所有可能性都分析列举出来。
确定边界：就是找到结束的条件
写出状态转移方程：即主问题和子问题的关系式
代码实现

BFS广度优先搜索

例题：数字三角形

! 在这里插入图片描述

思路分析：

先用一个二维数组来存储数据第一行一个数字，第二行2个数字····· 我们使用双重for循环来完成
只能加上左边或者右边的数字，那么就进行判断
如何求和呢，那么久累加，让上面一层数字加上下面左边或者右边的数字，那么最终两两比较再相加就能得到最大的数字

代码如下：

import java.util.Scanner;

public class Main_P22 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);  //输入
		System.out.println("请输入行数:");
		int n = scanner.nextInt();  //输入整数
		
		int [][] a = new int [n] [n]; //创建大小为 n 行 n 列的矩阵
		//输入矩阵数据
		for(int i = 0 ; i<n ; i++) {
			for(int j = 0 ;j<=i;j++) {
				a [i][j] = scanner.nextInt();
			}
		}
		//从第四行开始选择较大的数，然后主键从第到高
		for (int i = n-1; i > 0 ; i--) {
			for(int j = 0 ;j<i;j++) {
				//滚动数组最后a[0][0]为最大的和
				//选出左下角或者右下角大的数加上赋值给a[i-1][j]
				if((a[i-1][j]+a[i][j])  >  (a[i-1][j]+a[i][j+1])) {
				a[i-1][j]+=a[i][j]; //加上左边的
			}else {
				a[i-1][j]+=a[i][j+1];//加上右边的
			}
		}
	}
		System.out.println("最终最大和为："+a[0][0]);
		
}
}