动态规划(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/
爬到第⼀层楼梯有⼀种⽅法,爬到⼆层楼梯有两种⽅法(初始化)
那么第⼀层楼梯再跨两步就到第三层 ,第⼆层楼梯再跨⼀步就到第三层(推到)
所以到第三层楼梯的状态可以由第⼆层楼梯 和 到第⼀层楼梯状态推导出来,那么就可以想 到动态规划了
五步曲
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