背景
递归实现是出了名的消耗内存以及时间复杂度大，尤其是在有很多子问题重复计算的情况下。这个时候我们一般通过动态规划的手段，去做记忆性搜索，那么如何将递归转化成动态规划呢。我们来通过斐波那契数列这个例子来展开：
例子
斐波那契的递归实现：
private static long func(int n) {
if (n == 0 || n == 1){
return 1;
} else {
return func(n - 1) + func(n - 2);
}
}
斐波那契的DP实现：
private static long dpFunc(int n) {
//构建状态转移矩阵
long state[] = new long[n+1];
//初始化状态转移矩阵
state[0] = 1;
state[1] = 1;
//状态转移方程
for (int i=2;i<=n;i++) {
state[i] = state[i - 1] + state[i - 2];
}
return state[n];
}
步骤
递归到动规的一般转化方法：
1.创建状态转移矩阵
递归函数有n个参数，就定义一个n维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值
2.初始化状态转移矩阵
这样就可以从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。
3.状态转移方程
构建矩阵元素的新循环；
递归的方法名替换为矩阵名；递归的方法入参替换为矩阵元素；递归的方法返回参数替换为矩阵元素；
返回结果替换为矩阵中的末位元素。
