动态规划与贪心算法

前言

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

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

        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;
}
# 算法