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;
}