算法概念
- 动态规划（Dynamic Programming）是一种分阶段求解的算法思想，通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（分治）的方式去解决。
- 动态规划中有三个重点概念：
最优子结构：按照最佳的方式进行拆分，用来描述问题状态与状态之间的关系；
边界：问题的边界区域，可以是除了最优子结构的其它区域；
状态转移公式（递推公式）dp方程：根据最优子结构和边界终结出来的方程。 - 优缺点：
优点：时间复杂度和空间复杂度都相当较低
缺点：难，有些场景不适用
算法例子
斐波那契数列
规律：从第3个数开始，每个数等于前面两个数的和。
分析得知：
if(i<2) 则 dp[0] = 0，dp[1] = 1;
if(i>=2) 则 dp[i] = dp[i-1] + dp[i-2];
所以：
最优子结构：fib[9] = fib[8] + fib[7]
边界：a[0] = 0; a[1] = 1
dp方程：fib[n] = fib[n-1] + fib[n-2]
实现代码如下：
package com.xxliao.algorithms.dynamic_programming;
/**
* @author xxliao
* @description: 利用动态规划实现
* 斐波那契数列：0、1、1、2、3、5、8、13、21、34、55.....
* 规律：从第3个数开始，每个数等于前面两个数的和
*
* @date 2024/6/1 1:17
*/
public class Demo01 {
public static void main(String[] args) {
System.out.println(fib(9));
}
/**
* @description 动态规划实现 斐波那契数列
* @author xxliao
* @date 2024/6/1 1:23
*/
public static int fib(int n) {
// 定义当前数组，也就是0 ~ n 数组
int[] array = new int[n+1];
// 定义边界
array[0] = 0;
array[1] = 1;
// if(i>=2) 则 dp[i] = dp[i-1] + dp[i-2]; dp方程
int i = 2;
for(; i <= n; i++){
array[i] = array[i-1] + array[i-2];
}
return array[i-1]; // 循环结束加了1
}
}
演示结果：
