蓝桥杯算法 - 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]);
		
}
}

DFS深度优先搜索

欢迎关注!!!

上一篇:Python从入门到精通秘籍十六


下一篇:Zero-Change Object Transmission for Distributed Big Data Analytics——论文泛读