动态规划是一种算法, 通过将复杂问题分解为子问题来解决给定的复杂问题, 并存储子问题的结果, 以避免再次计算相同的结果.
以下是一个问题的两个主要特性, 表明可以使用动态规划解决给定的问题.
重复子问题
最佳子结构
重叠子问题:
像分而治之一样, 动态规划结合了子问题的解决方案. 动态规划主要用于解决一次又一次需要计算相同子问题的复杂问题. 在动态规划中, 子问题的计算解决方案存储在一个表中, 这样就不必重新计算. 所以当没有共同的 (重叠的) 子问题时, 动态规划是没有用的. 例如, 二分搜索没有共同的子问题. 如果我们以斐波纳契数的递归程序为例, 有许多子问题一次又一次地被解决.
- /* simple recursive program for Fibonacci numbers */
- int fib(int n)
- {
- if ( n <= 1 )
- return n;
- return fib(n-1) + fib(n-2);
- }
复制代码
Recursion tree for execution of fib(5)
我们可以看到函数 fib(3)被调用了 2 次. 如果我们已经存储了 fib(3)的值, 那么不用再次计算它, 而是可以重新使用旧的存储值. 有以下两种不同的方式来存储值, 以便这些值可以重复使用:
- Memoization(自上而下)
- Tabulation(自下而上)
- Memoization(自上而下)
一个问题的 memoized 程序类似于递归版本, 只是在计算解决方案之前查看一个查找表. 我们初始化一个所有初始值为 NIL 的查找数组. 每当我们需要解决一个子问题, 我们首先查找查找表. 如果预先计算的值在那里, 那么我们返回该值, 否则我们计算该值并将结果放在查找表中, 以便稍后可以重新使用.
以下是第 n 个斐波纳契数的 Memoization 版本.
- public class Fibonacci {
- final int MAX = 100;
- final int NIL = -1;
- int lookup[] = new int[MAX];
- void _initialize() {
- for (int i = 0; i <MAX; i++) {
- lookup[i] = NIL;
- }
- }
- int fib(int n) {
- if (lookup[n] == NIL) {
- if (n <= 1)
- lookup[n] = n;
- else
- lookup[n] = fib(n - 1) + fib(n - 2);
- }
- return lookup[n];
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- Fibonacci f = new Fibonacci();
- int n = 10;
- f._initialize();
- System.out.println(f.fib(n));
- }
- }
复制代码
Tabulation(自下而上)
给定问题的表格程序以自下而上的方式构建一个表, 并从表中返回最后一个条目. 例如, 对于相同的斐波纳契数, 我们首先计算 fib(0), 然后计算 fib(1), 然后计算 fib(2), 然后计算 fib(3)等等. 所以从字面上看, 我们正在自下而上地构建子问题的解决方案.
以下是第 n 个斐波纳契数字的表格版本.
- public static int fib(int n) {
- int f[] = new int[n + 1];
- f[0] = 0;
- f[1] = 1;
- for (int i = 2; i <= n; i++) {
- f[i] = f[i - 1] + f[i - 2];
- }
- return f[n];
- }
复制代码
尝试以下问题作为练习. 1)为 LCS(最长公共子序列)问题写一个 Memoized 解决方案. 请注意, Tabular 解决方案在 CLRS 书中给出. 2)你如何选择 Memoization 和 Tabulation?
Tabulation vs Memoization
最优子结构
给定问题具有最优子结构性质, 如果给定问题的最优解可以通过使用子问题的最优解得到. 例如, 最短路径问题具有以下最佳的子结构属性: 如果节点 x 位于从源节点 u 到目的节点 v 的最短路径, 那么从 u 到 v 的最短路径是从 u 到 x 的最短路径和从 x 到 v 的最短路径的组合. 标准的 All Pair Shortest Path 算法如 Floyd-Warshall 和 Bellman-Ford 都是动态规划的典型例子. 最长路径问题没有最佳子结构属性.
- 1 + 1 +1 + 1 +1 + 1
- 1 + 1 +1 + 3
- 1 + 1 +3 + 1
- 1 + 3+ 1 + 1
- 3 + 1+ 1 + 1
- 3 + 3
- 1 + 5
- 5 + 1
- int solve(int n){
- if(n <0)
- return 0;
- if(n == 0)
- return 1;
- return solve(n-1) + sovle(n-3) + solve(n-5);
- }
- Adding memoization or tabulation for the state
- // initialize to -1
- int dp[MAXN];
- // this function returns the number of
- // arrangements to form 'n'
- int solve(int n)
- {
- // base case
- if (n < 0)
- return 0;
- if (n == 0)
- return 1;
- // checking if already calculated
- if (dp[n]!=-1)
- return dp[n];
- // storing the result and returning
- return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
- }
- Tabulation vs Memoizatation
- Tabulation Method - Bottom Up Dynamic Programming
- public class BagObject {
- public int capaticy;
- public int value;
- public BagObject(int cap, int val) {
- // TODO Auto-generated constructor stub
- this.capaticy = cap;
- this.value = val;
- }
- }
- public class PackageProblem {
- private int cap;
- private BagObject[] objs;
- private int[][] dp;
- public PackageProblem(int bagCap, BagObject[] objs) {
- // TODO Auto-generated constructor stub
- cap = bagCap;
- this.objs = objs;
- dp = new int[this.objs.length][cap];
- }
- public int getMaxValue() {
- int nowval = objs[0].value;
- int nowcap = objs[0].capaticy;
- int i, j;
- for (i = 0; i < cap; i++) {
- if (i + 1>= nowcap && dp[0][i] <nowval) {
- dp[0][i] = nowval;
- }
- }
- for (i = 1; i < this.objs.length; i++) {
- nowcap = objs[i].capaticy;
- nowval = objs[i].value;
- for (j = 0; j < cap; j++) {
- if (j + 1 - nowcap> 0) {
- dp[i][j] = Math.max(dp[i - 1][j], nowval + dp[i - 1][j + 1 - nowcap]);
- } else {
- dp[i][j] = Math.max(dp[i - 1][j], nowval);
- }
- }
- }
- return dp[objs.length - 1][cap - 1];
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- BagObject guiter = new BagObject(1, 1500);
- BagObject tap = new BagObject(3, 2000);
- BagObject radio = new BagObject(4, 3000);
- BagObject[] objs = new BagObject[3];
- objs[1] = guiter;
- objs[0] = tap;
- objs[2] = radio;
- PackageProblem pp = new PackageProblem(4, objs);
- System.out.println(pp.getMaxValue());
- }
- }
- public class LongCS {
- public static int lcs(String a, String b) {
- int[][] dp = new int[a.length() + 1][b.length() + 1];
- for (int i = 1; i < a.length() + 1; i++) {
- for (int j = 1; j < b.length() + 1; j++) {
- if (a.charAt(i - 1) == b.charAt(j - 1)) {
- dp[i][j] = dp[i - 1][j - 1] + 1;
- } else {
- dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
- }
- }
- }
- return dp[a.length()][b.length()];
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- System.out.println(lcs("AGGTAB", "GXTXAYB"));
- }
- }
来源: https://juejin.im/post/5b6bba105188251ace75efc7