Dynamic Programming
Dynamic Programming 算法-动态规划 Dynamic Programming–从菜鸟到老鸟-CSDN博客 拆分子问题，记住过往，减少重复计算 1.最优子结构 如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。 2.重叠子问题 在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次，在求cut（4）的时候cut（0）被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。 自顶向下备忘录 自底向上动态规划 public int minPathCost(int[][] grid, int[][] moveCost) { int[] cost = new int[grid[0].length]; int min_cost = 0x7fffffff; for(int i=0;i<cost.length;i++){ cost[i] = grid[grid.length-1][i]; } // hop loop for(int i=grid.length-2;i>=0;i--){ // update cost loop for(int j=0;j<cost.length;j++){ min_cost = 0x7fffffff; for(int k=0;k<moveCost[grid[i][j]].length;k++){ min_cost = Math.min(moveCost[grid[i][j]][k]+grid[i][j], min_cost); } cost[j] = min_cost; } } for(int i=0;i<cost.length;i++){ min_cost = Math.min(min_cost, cost[i]); } return min_cost; }