动态规划与贪心算法

前言

之前已经写过一篇关于贪心算法的博文（地址，即：在当前现有的情况下选择最优的选项，表面看来，这样进行操作的确整体会是最优。但真的是这样吗？

蒜头在玩一款游戏，他在一个山顶，现在他要下山，山上有许多水果，蒜头每下一个高度就可以捡起一个水果，并且获得水果的能量。

        fruits = new int[][]{
            {3,0,0,0},
            {1,2,0,0},
            {6,2,3,0},
            {3,5,4,1}    
            
    };

 如上图，是一个二维数组，题目是从(0,0)处开始，往下进行“捡水果”，只能选择自己附近的两个，就是说，当前在(0,0)只能走(1,0)和(1,1)两条路，问最多可以获得多少能量？这个时候我们使用贪心算法便会得到结果为13。而答案却是15。

这样贪心算法的缺点就显露出来了，它只能保证它是相对的最优，确不是整体的最优。

如何解决？这里就要说到动态规划了。

动态规划的主要思想是，将一个大问题分解成很多小问题，然后通过小问题进行推导出结果,而因为它分析了每一个小问题，所以结果必然是最优的。

  如上面的代码如果运用动态规划，它会分析，如果选择了(1,0)会怎么样，如果选择了(1,1)又会怎么样？ 然后我们使用Math.max(f(1,0),f(1,1))方法进行判断，是前者大还是后者大。而这个方法呢，是一个递归的过程，f(1,0)里接下来会继续分解，如果选择了(2,1)会怎么样，选择了(2,2)会怎么样？
  一直到数组的结尾为出口，发现(3,1)比(3,0)大，然后返回返回到计算f(2,0)这个方法中。以此类推，得到f(1,0)比f(1,1)大的结果，所以加上(0,0)便是最终结果。

    public static int f(int x,int y){
    if (x > 3 || y > 3) {
        return 0;
    }
    int A = f(x+1,y);
    int B = f(x+1,y+1);
    return fruits[x][y] + Math.max(A, B);
}

  值得一说的是，如果我们使用上图这样的代码结构来讲的话，会造成很多重复子问题。比如当程序走到(1,0)的时候，会去递归到(2,1)，而(1,1)也会递归到(2,1)。
  如何解决？
  因此，我们一般这样编写动态规划算法的时候会使用一个数组进行存储，先判断有没有已经递归过了。

    public static int f(int x,int y){
    if (x > 3 || y > 3) {
        return 0;
    }
    int max;
    if (vis[x][y] != 0) {
        max = vis[x][y];
    }else {
        max = vis[x][y] = Math.max(f(x+1,y), f(x+1,y+1));
    }
    return fruits[x][y] + max;
}