动态规划(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深度优先搜索
欢迎关注!!!