[关闭]
@iar 2015-10-29T00:19:35.000000Z 字数 6160 阅读 141

Report: POJ 1088-滑雪-经典DP

POJ DP

题目链接
+ 经典的DP问题. 类似的有max triangle sum. 这类题目是找最值, 并且到达每个点有多种路径. 所以是DP. 还有个关键就是DP的3个条件. 以及4要素.

复习DP

DP的2个解法: wiki

  1. Top-down approach: This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its sub-problems, and if its sub-problems are overlapping, then one can easily memoize or store the solutions to the sub-problems in a table. Whenever we attempt to solve a new sub-problem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the sub-problem and add its solution to the table.
  2. Bottom-up approach: Once we formulate the solution to a problem recursively as in terms of its sub-problems, we can try reformulating the problem in a bottom-up fashion: try solving the sub-problems first and use their solutions to build-on and arrive at solutions to bigger sub-problems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems. For example, if we already know the values of F41 and F40, we can directly calculate the value of F42.

DP的3个条件

  1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
  2. 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
  3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

分析题目

方法1: beeder

  1. node[][]如下:
  2. 1 5 6
  3. 9 4 7
  4. 2 3 8
  6. 计算完res00后, path是:
  7. 5 4 3
  8. 1 0 2
  9. 0 0 1
  10. ------
  11. reset path[][], 计算res20, path是: 因为到达[2,0]的最优解是7.
  12. 0 4 3
  13. 1 5 2
  14. 7 6 1
  15. 接着计算完res10后, path是: 因为没有到达[1,0]的点, 所以返回rs+1= 1.
  16. 0 4 3
  17. 1 5 2
  18. 7 6 1
  19. 而不是
  20. 0 0 0
  21. 1 0 0 
  22. 0 0 0
  23. 还有很重要的点就是: 从上面可以看出来每个子问题计算完之后就是最后的值, 例如[0,0]的最优解是5, 并不会因为我call helper(node, path, 1,0)而改变. 因为很简单: 到达每个点的最优解只有1个!
  1. private int helper(int[][] node, int[][] path, int r, int c) {
  2.     // 居然没有base case? 因为这个是求最值的DP, 类似于smilence的笔记里面所说的聚合问题(我觉得应该叫发散, 因为是从要求的点[i,j], 发散求出所有子问题的解, 然后再聚合回到这个点). 所以是topdown, 但不是backtracking.
  3.     int rs = 0;
  4.     for (int i = 0; i < 4; ++i) {
  5.         int next_r = r + dx[i];
  6.         int next_c = c + dy[i];
  7.         if (isValid(node, r, c, next_r, next_c)) {
  8.             if (path[next_r][next_c] > 0) {
  9.                 rs = Math.max(path[r][c], path[next_r][next_c]+1); 
  10.             }
  11.             else {
  12.                 rs = Math.max(path[r][c], helper(node, path, next_r, next_c) + 1);
  13.             }
  14.         }
  15.     }
  16.     return path[r][c] = rs+1;
  17. }

怎么写递归?

怎么递归调用?

方法2: douban

  1. private int helperDouban(int[][] node, int[][] path, int r, int c) {
  2.     if (path[r][c] > 0) {
  3.       return path[r][c];
  4.     }
  6.     for (int i = 0; i < 4; ++i) {
  7.       int next_r = r + dx[i];
  8.       int next_c = c + dy[i];
  9.       if (isValid(node, r, c, next_r, next_c, node.length, node[0].length)) {
  10.         path[r][c] = Math.max(path[r][c], helperDouban(node, path, next_r, next_c) + 1);
  11.       }
  12.     }
  14.     return path[r][c];
  15. }

递归

  1. 1  2  3  4
  2. 12 13 14 5
  3. 11 16 15 6
  4. 10 9  8  7

如果要求返回最优方案, 不仅仅是最优解

往往DP问题是求解最优解. 即1个值而已. 然后follow up常考返回得到最优解的最优方案, 例如路径之类的.
+ 有2个方法: 一个就是ALgorithm Stanford的课一样, 通过DP table, 一个个找回去到起点. 还有一个方法就是在DP的过程中update 最优方案.

方法1 // TODO

方法2

  1. private int helperP(int[][] node, int[][] path, List<Integer>[][] list, int r, int c) {
  2.     int rs = 0;
  4.     int lastSize = 0;
  5.     for (int i = 0; i < 4; ++i) {
  6.       int rr = r + dx[i];
  7.       int cc = c + dy[i];
  8.       if (isValid(node, r, c, rr, cc, node.length, node[0].length)) {
  9.         if (path[rr][cc] != 0) {
  10.           if (rs < path[rr][cc]) {
  11.             for (int id = 0; id < lastSize; ++id) {
  12.               list[r][c].remove(list[r][c].size() - 1);
  13.             }
  14.             list[r][c].addAll(list[rr][cc]); //add(node[rr][cc]); //
  15.             lastSize = list[rr][cc].size();
  16.             rs = path[rr][cc];
  17.           }
  18.         }
  20.         else {
  21.           int tmp = helperP(node, path, list, rr, cc);
  23.           if (tmp > rs) {
  24.             rs = tmp;
  25.             for (int id = 0; id < lastSize; ++id) {
  26.               list[r][c].remove(list[r][c].size() - 1);
  27.             }
  28.             list[r][c].addAll(list[rr][cc]); // add(node[rr][cc]);
  29.             lastSize = list[rr][cc].size();
  30.           }
  31.         }
  32.       }
  33.     }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注