动态规划问题的五步操作：
动态规划就是把dp表填满，则最终一定有一个数据是我们所需要的数据
下面以一道简单的题目进行讲解
本题其实就是斐波那契数列的一个plus版 ，就是利用递推关系求值的过程
1.前期准备：创建dp表(使用一维数组)
正式过程
1.状态表示
状态表示就是找dp[i]所表示的含义，本体比较简单，根据题目要求我们知道状态表示就是对应的泰波那契数
2.状态转移方程
状态转移方程就是去找dp[i]与其他状态之间的依赖关系，本题的依赖关系题目直接给出，就是递推公式
3.初始化
初始化是保证填表时不越界，初始化的根据是状态转移方程，对于本题来说，由于方程中出现了i-1,i-2,i-3,所以i不能等于0,1,2,如果等于就发生了越界，所以先进行初始化，把可能发生越界的位置初始化(本题根据题目要求直接进行初始化)
4.确定填表顺序
填表顺序是为了保证插入状态时所需要的状态已经被计算过，比如在本题中，如果要在下标为4的地方进行插入，需要保证下标为1，2，3对应的状态已经被计算过。所以本题的填表顺序就是从左往右依次填入
5.填表，返回
题目要求+状态表示
题目要求返回第n个泰波那契数，状态表示dp[n]就是 第n个泰波那契数，所以直接返回即可
对于动态规划的题目来说，前两部是最重要的，找到对应的状态表示和状态转移方程是解决动态规划问题的核心
代码实现：
写代码一般分为4步
1.创建dp表
2.初始化(防止越界)
3.填表
4.返回
class Solution {
public int tribonacci(int n) {
// 1.创建dp表
// 2.初始化(防止越界)
// 3.填表
// 4.返回
// 处理细节
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int[] dp = new int[n+1];
dp[0]=0;dp[1]=dp[2]=1;
for(int i = 3; i <= n; i++) {
// 状态转移方程+填表顺序
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
return dp[n];
}
}时间复杂度:O(N)
空间复杂度:O(N)
优化思路：
本题的优化可以使用滚动数组来降低空间复杂度至O(1)，常用到本类型的题和背包问题
滚动数组的使用条件：当你发现求解某个状态时，只需若干个有限的状态来辅助，此时就可以使用滚动数组
代码实现：
class Solution {
public int tribonacci(int n) {
// 1.创建dp表
// 2.初始化(防止越界)
// 3.填表
// 4.返回
// 处理细节
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int a=0,b=1,c=1,d=0;
for(int i = 3; i <= n; i++) {
// 状态转移方程+填表顺序
d = a+b+c;
a = b;
b = c;
c = d;
}
return d;
}
}02.不同的路径(经典的二维dp问题)
代码:
class Solution {
public int uniquePaths(int m, int n) {
// 1.准备dp表
int[][] dp = new int[m + 1][n + 1];
// 2.初始化
dp[0][1] = 1;
// 3.填表
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
}
