算法之动态规划
标签:算法
介绍
动态规划(Dynamic Programming,简称DP)算法是一种通过将问题(比较复杂)划分为相互重叠的子问题(简单易于求解),并解决子问题来解决原问题的方法。它通常用于优化问题,其中需要找到最优解或最大/最小值。
动态规划算法的一般步骤如下:
- 定义子问题:将原问题划分为若干子问题,这些子问题应具有最优子结构的特性,即原问题的最优解可以通过子问题的最优解推导出来。
- 构建状态转移方程:通过观察子问题之间的关系,定义状态和状态之间的转移方式。这个方程描述了问题的最优解如何由子问题的最优解计算得出。
- 确定边界条件:确定最简单的子问题的解,也就是边界条件。这些边界条件将作为递归或迭代的终止条件。
- 解决子问题:按照定义的状态转移方程,从最简单的子问题开始逐步解决更复杂的子问题,直到解决原问题。
- 记忆化或建表:为了避免重复计算,可以使用记忆化技术将子问题的解存储起来,或者使用表格/数组记录子问题的解。
- 求解原问题:通过解决子问题,得到原问题的最优解。
动态规划算法的关键在于将复杂问题划分为可解决的子问题,并通过递归或迭代的方式解决子问题。通过记忆化或建表,可以避免重复计算,提高效率。动态规划算法通常具有较高的时间复杂度,但通过合理的状态定义和状态转移方程设计,可以将问题的复杂度降低到可接受的范围内。
动态规划算法在解决一些经典问题中具有广泛应用,如背包问题、最短路径问题、最长公共子序列问题等。它也被广泛应用于算法设计和优化领域,为解决复杂问题提供了一种有效的方法。
常见题型
斐波拉契数
斐波那契数 (通常用 F(n)
表示)形成的序列称为 斐波那契数列 。该数列由 0
和 1
开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
public class _1FeiBoNaQi {
public static void main(String[] args) {
//[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(calculate1(i));
}
System.out.println(list);
}
public static int calculate1(int n) {
if (n < 2) {
return n;
}
if (n == 2) {
return 1;
}
// 1.确定dp数组以及含义 nums[0]表示第1个斐波拉契数,nums[1]表示第2个斐波拉契数,nums[i]表示第i+1个斐波那契数
int[] nums = new int[n + 1];
// 3.初始化dp数组
nums[0] = 0;
nums[1] = 1;
nums[2] = 1;
// 4.确定遍历顺序
for (int i = 3; i < n + 1; i++) {
// 2.推到公式
nums[i] = nums[i - 1] + nums[i - 2];
}
return nums[n];
}
public static int calculate2(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
// 为啥非要从下标0开始,抛弃0从1开始也可以,就认为第一个值是1,第二个值也是1(两个初始值)
int fn_2 = 1, fn_1 = 1, fn = 0;
for (int i = 0; i < n - 2; i++) {
//第3个数的值等于前两个数的和
fn = fn_2 + fn_1;
//第2个数的值赋值给第1个数
fn_2 = fn_1;
//第3个数的值赋值给第2个数
fn_1 = fn;
}
return fn;
}
}
[0, 1, 1, 2, 3, 5]
爬楼梯问题
假设你正在爬楼梯。需要 n
(n为正整数) 阶你才能到达楼顶。每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
https://leetcode.cn/problems/climbing-stairs/
爬到第⼀层楼梯有⼀种⽅法,爬到⼆层楼梯有两种⽅法(初始化)
那么第⼀层楼梯再跨两步就到第三层 ,第⼆层楼梯再跨⼀步就到第三层(推到)
所以到第三层楼梯的状态可以由第⼆层楼梯 和 到第⼀层楼梯状态推导出来,那么就可以想
到动态规划了
五步曲
-
确定dp数组以及下标的含义
dp[i]: 爬到第i层楼梯,有dp[i]种⽅法 -
确定推到公式
从dp[i]的定义可以看出,dp[i] 可以有两个⽅向推出来。
⾸先是dp[i – 1],上i-1层楼梯,有dp[i – 1]种⽅法,那么再⼀步跳⼀个台阶不就是dp[i]了么。
还有就是dp[i – 2],上i-2层楼梯,有dp[i – 2]种⽅法,那么再⼀步跳两个台阶不就是dp[i]了么。
那么dp[i]就是 dp[i – 1]与dp[i – 2]之和!
所以dp[i] = dp[i – 1] + dp[i – 2] -
dp数组如何初始化
dp[1]=1;爬到1层有1中爬法
dp[2]=2;爬到2层有2种爬法
-
确定遍历顺序
从递推公式dp[i] = dp[i – 1] + dp[i – 2];中可以看出,遍历顺序⼀定是从前向后遍历的
-
举例推到dp数组
public class PaLouTi {
public static void main(String[] args) {
// 0 1 1 2 3 5
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(calculate(i));
}
System.out.println(list);
}
public static int calculate(int n) {
if (n < 3) {
return n;
}
// 1.确定dp数组以及意义:dp数组dp[i],表示第i个层有dp[i]中爬法
int[] dp = new int[n + 1];
// 3.初始化dp数组 (不一定非要从dp[0]开始,也不一定非要初始化2个数)
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
// 4.确定遍历顺序
for (int i = 3; i < n + 1; i++) {
// 2.推到公式
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
爬楼梯和斐波拉契比较
1.斐波拉契f(1)=1,f(2)=1
2.爬楼梯f(1)=1,f(2)=2
3.递推公式都是f(n)=f(n-1)+f(n-2)
爬楼梯之最小消费
题目描述:
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。请你计算并返回达到楼梯顶部的最低花费。把题看懂是多么重要的一种能力呀(狗头,反过来说,把题描述清楚是多么重要的一种能力呀)
public class _3PaLouTi2 {
public static void main(String[] args) {
/**
* [1,100,1,1,1,100,1,1,100,1]
* [0] 从第0阶往上阶跳需要1
* 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用
*/
//
System.out.println(xxx(new int[]{1,100,1,1,1,100,1,1,100,1}));
System.out.println(xxx(new int[]{10,15,20}));
}
private static int xxx(int[] cost) {
// dp数组
int[] dp = new int[cost.length+1];
// 第一阶的最小值
dp[1]=cost[0];
// 第二阶的最小值
dp[2]=Math.min(cost[0], cost[1]);
// 第三阶的最小值
dp[3] = Math.min(cost[2] + dp[2], cost[1] + dp[1]);
if(cost.length<3){
return dp[cost.length-1];
}
for (int i = 3; i < cost.length+1; i++) {
// 第n阶的最小值
dp[i] = Math.min(cost[i - 1] + dp[i-1], cost[i - 2] + dp[i-2]);
}
return dp[dp.length-1];
}
}
6
25
背包问题
打家劫舍
股票问题
子序列问题
动归五部曲
dp数据以及下标的含义
递推公式
dp数组如何初始化
遍历顺序
打印dp数组
版权声明:本文为博主作者:JAVA领域优质创作者原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/weixin_41883161/article/details/136507113