动态规划算法简介
动态规划，英文名Dynamic Programming，是一种把原问题分解为相对简单的子问题以求解的方法。
动态规划为了避免多次解决重复的子问题，子问题的结果都被保存，直到整个问题得以解决。
动态规划算法：每次决策依赖于当前状态，个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
动态规划算法基本思想
动态规划算法的思想比较简单，其实质是分治思想和解决冗余，因此它与分治法和贪心法类似。
动态规划是把原问题分解为若干子问题，自底向上，先求解子问题，把结果存储在表格中。
在求解大问题时直接从表格中查询小问题的解，避免重复计算，从而提高算法效率。
动态规划算法步骤
动态规划的设计都有着一定的模式，一般要经历以下4个步骤：
1）划分阶段
按照问题的特征，把问题分为若干阶段，划分后的阶段一定是有序的或者可排序的。
2）确定状态和状态变量
将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性。
3）确定决策并写出状态转移方程
状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程。
4）寻找边界条件
状态转移方程是一个递推式，因此需要找到递推终止的条件。
动态规划算法基本框架
for(j=1; j<=m; j=j+1) // 第一个阶段
xn[j] = 初始值;
for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段
for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式
xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案
print(x1[j1]);
for(i=2; i<=n-1; i=i+1）
{
t = t-xi-1[ji];
for(j=1; j>=f(i); j=j+1)
if(t=xi[ji])
break;
}
动态规划算法经典例子
斐波那契数列是最经典的动态规划算法应用实例之一，接下来将从斐波那契数列入手，学习下基于动态规划求解问题。
1.问题描述
斐波那契数列又译为费波拿契数、斐波那契数列、费氏数列、黄金分割数列。
用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。
比如：
0,1,1,2,3,5,8,13,21,34,55,89 ...
从中我们可以发现从第三个数开始的值是前两个值的和。
2.基本思路
根据斐波那契数列公式，在数列个数大于2的情况下，后一项的值等于前两项的值的和。
也就是说，问题的求解依赖其子问题的求解，显然这个问题可以使用递归算法解决。
但是，也应注意到该递归算法会反复地求解相同的子问题，而不是一直生成新的子问题，而动态规划通过安排问题的求解顺序，确保每个子问题只求解一次。
将结果保存起来，如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算，所以，可以使用动态规划求解该问题。
3代码示例
public int fibInDynamicProgramming(int n) {
if (n < 2) {
return n;
}
// 暂存中间结果
int first = 0;
int second = 1;
int result = first + second;
for (int i = 2; i <= n; i++) {
result = first + second;
first = second;
second = result;
}
return result;
}
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》