动态规划(Dynamic Programming)
马上要考算法了，复习了动态规划的内容，现作出笔记，加深印象。
概述
- 动态规划（DP）是通过组合子问题的解而解决整个问题。动态规划是一种规则，一种思考问题的方式，而不是指程序编码
- 动态规划适用于子问题不是独立的情况，即各子问题包含公共的子子问题
- 使用分治法则会重复的计算子问题，而动态规划对每个子问题只求解一次，将结果保存在一张表中，避免多次遇到各个子问题时重新计算结果。
- 动态规划通常应用于最优化问题。
- 动态规划通常基于一个递推公式及一个或多个初始状态；当前子问题的解由上一个子问题的解推出。
算法设计步骤（参考算法导论）
- 描述最优解的结构
- 递归定义最优解的值
- 按自底向上的方式计算最优解值
- 由计算的结果构建最优解
如何找状态转移方程
- 找出问题的“状态”
- 达到这种“状态”有几种方式
- 写出状态转移方程（欲求问题的解，先求子问题的解）
实际应用
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
典型的动态规划问题，求解如下：
目标：青蛙跳到第n级的台阶，总的跳法。
假设：f(n)表示青蛙跳到n台阶的总跳法（问题的状态)，则青蛙可从（n-1）级台阶直接跳上，也可从（n-2）,(n-3)···3,2,1,0级台阶直接跳上（即达到这状态有几种方式），故f(n) = f(n-1)+f(n-2)+f(n-3)···+f(2)+f(1)+f(0)(状态方程）。
当 n=1时，只有一种跳法，f(1) = 1;
当 n=2时，会有两种跳法，一次1阶或2阶，f(2) =f(1)+f(0);
当 n=3时，会有三种跳法，f(3) =f(2)+f(1)+f(0);即，第一次由2级台阶跳上；第二次由一级台阶直接跳上；第三次跨越3个台阶直接跳上。
由于 f(n-1) = f(n-2)+f(n-3)+···f(2)+f(1)+f(0)，则状态方程化简为：f(n)=2*f(n-1)。
故可得递归式：
f(n) = 0 (n=0) f(n) = 1 (n=1) f(n) = 2*f(n-1) (n>=2)
Java实现
public class DP {
public int JumpFloorII(int target) {
if(target <= 0) return 0;
int[] jump = new int[target + 1];
jump[1] = 1;
for(int i = 2 ; i <= target ; i++){
jump[i] = 2 * jump[i - 1];
}
return jump[target];
}
}
参考资料
- 《算法导论》
- 动态规划：从新手到专家