递归写法

或者

 

也会很多重叠的问题

1、记忆化搜索

 

2、动态规划

 

斐波那契数列，就是从爬楼梯里面总结出来的。

 

经典的动态规划问题

 

有时候记忆化搜索会比较难写出递归的代码，比如这道题。

 

求【2】的最短路径，其实就i是求【3】【4】里面的最短路径，就是求【6】，【5】，【7】的最短路径，然后最后一列的最短路径就是他自己。

这样会有重复的部分，重复的就放在记忆化搜索数组里面就好。

其实这个递归代码并不好写。

那么记忆化想出来了，怎么改成动态规划？

从基本问题入手，可以想到，对于第三层来说，最短路径就是当前数字+下一层相邻里面最小的数字。

对第二层来说，也是这样。

所以就可以写出一个循坏的代码（动态规划更像循环）

可以用一个数组，记录每一行的最小值，但是这样好像比较麻烦，

干脆直接覆盖原数组，因为算出最小值之后，原来的数字就没有用了。

我的代码。

int len = triangle.size();        //最后一行不用改        //从倒数第二行开始        for(int i=len-2;i>=0;i--){            List
     
       current = triangle.get(i);            List
      
        next = triangle.get(i+1);            //看他的排布状况，不是开头对齐排列的，相邻好像就+0，+1            //当前这个数字的最短路径 = 当前数字+min{last(当前+0，当前+1)}            int index = current.size();            for(int j=0;j
      
     

一次通过美滋滋

 

 

 

这个题其实也很简单。

求a11的最短路径，其实就是求a12和a21的最短路径，然后选这里面最小的就是了。

然后递归代码也不好写。

怎么办呢？那就从最后往上加上去。

最后一行没法向下走，所以最后一行的最短路径都是直接加上右边。

最右列的元素，就是直接加上下边。

然后直接覆盖原值。

所以对于普通元素，就是看右边和下边哪个小就好了。

最后【0】【0】就是答案

//从最后一个算起        int row = grid.length-1;        int column = grid[0].length-1;        for(int i=row;i>=0;i--){            for (int j=column;j>=0;j--){                if(i==row&&j==column){                    continue;                }else if (i==row){                    //如果是最后一行，就没法向下走了，那么最短路径就是直接加上右边                    int right = grid[i][j+1];                    grid[i][j]+=right;                }else if(j==column){                    //如果是最右一列，就没法往右走了，那么最短路径就是直接加上下面                    int next = grid[i+1][j];                    grid[i][j]+=next;                }else {                    //选右边的下边里，最短的路径                    int right = grid[i][j+1];                    int next = grid[i+1][j];                    if(right

一次通过美滋滋