算法之动态规划
算法之动态规划
标签:算法
介绍
动态规划（Dynamic Programming，简称DP）算法是一种通过将问题(比较复杂)划分为相互重叠的子问题(简单易于求解)，并解决子问题来解决原问题的方法。它通常用于优化问题，其中需要找到最优解或最大/最小值。
动态规划算法的一般步骤如下：
- 定义子问题：将原问题划分为若干子问题，这些子问题应具有最优子结构的特性，即原问题的最优解可以通过子问题的最优解推导出来。
- 构建状态转移方程：通过观察子问题之间的关系，定义状态和状态之间的转移方式。这个方程描述了问题的最优解如何由子问题的最优解计算得出。
- 确定边界条件：确定最简单的子问题的解，也就是边界条件。这些边界条件将作为递归或迭代的终止条件。
- 解决子问题：按照定义的状态转移方程，从最简单的子问题开始逐步解决更复杂的子问题，直到解决原问题。
- 记忆化或建表：为了避免重复计算，可以使用记忆化技术将子问题的解存储起来，或者使用表格/数组记录子问题的解。
- 求解原问题：通过解决子问题，得到原问题的最优解。
动态规划算法的关键在于将复杂问题划分为可解决的子问题，并通过递归或迭代的方式解决子问题。通过记忆化或建表，可以避免重复计算，提高效率。动态规划算法通常具有较高的时间复杂度，但通过合理的状态定义和状态转移方程设计，可以将问题的复杂度降低到可接受的范围内。
动态规划算法在解决一些经典问题中具有广泛应用，如背包问题、最短路径问题、最长公共子序列问题等。它也被广泛应用于算法设计和优化领域，为解决复杂问题提供了一种有效的方法。
常见题型
斐波拉契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1public 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