专栏首页光城(guangcity)LeetCode动态规划上之递归+记忆化搜索+DP逐步进阶(上)

LeetCode动态规划上之递归+记忆化搜索+DP逐步进阶(上)

LeetCode动态规划上之递归+记忆化搜索+DP逐步进阶(上)

类似题目:

  • 53.最大子序和
  • 70. 爬楼梯
  • 120. 三角形最小路径和

1.53.最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

实现思路:

递推式:动态规划:s(n)=Math.max(s(n-1)+nums[n],nums[n])

实现:

class Solution {
    public int maxSubArray(int[] nums) {
        int sum=0;
        int maxsum=nums[0];
        for(int num:nums){
            sum=Math.max(num,sum+num);
            maxsum = Math.max(sum,maxsum);
        }
        return maxsum;
    }
}

实现思路:

二分法:不断将区间划分为左、中、右!中间直接计算,左与右递归处理。

实现:

class Solution {
   public int maxSubArray(int[] nums) {
        int res;
        if(nums.length==0) return 0;
        res = maxSub(nums,0,nums.length-1);
        return res;
    }

    public int maxSub(int[] nums, int left, int right){
        if(left>right) return Integer.MIN_VALUE;
        if(left==right) return nums[left];
        int mid=(left+right)/2;
        int l=maxSub(nums,left,mid-1);//求左半边最大子序和
        int r=maxSub(nums,mid+1,right);//求右半边最大子序和
        int t=nums[mid];
        int max_num=nums[mid];
        for(int i=mid-1;i>=left;i--)//整合左半部分
        {
            t+=nums[i];
            max_num=Math.max(max_num,t);
        }
        t=max_num;
        for(int i=mid+1;i<=right;i++)//整合右半部分
        {
            t+=nums[i];
            max_num=Math.max(max_num,t);
        }
        return Math.max(Math.max(r,l),max_num);
    }
}

2.70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

实现思路:

直接递归:因为有众多重复计算,所以通不过!

实现:

class Solution {
    public int climbStairs(int n) {
        if(n==1||n==0){
            return 1;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

实现思路:

递归加缓存memo,由于每次计算都有许多重复计算,比如f4=f3+f2,f5=f4+f3,f4与f3被多次计算,如果能够在第一次的时候保存下来,后面直接访问,岂不是效率会高。

实现:

class Solution {

    public int climbStairs(int n) {
        int[] memo = new int[n+1];
        return fibStair(memo,n);
    }

    public int fibStair(int[] memo,int n){
        if(n==1||n==0){
            memo[n]=1;
        }else if(memo[n]==0){
            memo[n]=fibStair(memo,n-1)+fibStair(memo,n-2);            
        }
        return memo[n];
    }
}

实现思路:

动态规划:自底向上。

实现:

class Solution {

    public int climbStairs(int n) {
        int[] memo=new int[n+1]; 
        memo[0]=memo[1]=1;
        for (int i=2;i<=n;i++){
            memo[i]=memo[i-1]+memo[i-2];
        }
        return memo[n];
    }

};

递归:自顶向下。

实现:

class Solution {
    public int minPathSum(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        int res = fibPath(grid, m - 1, n - 1);

        return res;
    }

    public int fibPath(int[][] grid, int i, int j) {
        //左上角
        if (i == 0 && j == 0) {
            return grid[i][j];
        }
          //第一行
        if (i==0&&j == 1) {
            return grid[i][j] + grid[0][0];
        } else if (j==0&&i == 1) { //第一列
            return grid[0][0] + grid[i][j];
        }
        //递归第一列
        if (i > 0 && j == 0) {
           return fibPath(grid, i - 1, j) + grid[i][j];
        } else if (j > 0 && i == 0) { //递归第一行
            return fibPath(grid, i, j - 1) + grid[i][j];
        }
        //递归中间部分
        return Math.min(fibPath(grid, i, j - 1), fibPath(grid, i - 1, j)) + grid[i][j];
    }
}

实现思路:

递归+记忆化搜索法:自顶向下。新开一个存储空间即可。

实现:

class Solution {
    public int minPathSum(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        int[][] memo = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                memo[i][j] = -1;
            }
        }
        memo[0][0] = grid[0][0];
        return fibPath(memo, grid, m - 1, n - 1);
    }

    public int fibPath(int[][] memo, int[][] grid, int i, int j) {
        if (i == 0 && j == 0) {
            return grid[i][j];
        }
        if (memo[i][j] != -1) {  //记忆搜索存储条件
            return memo[i][j];
        }
        if (i==0&&j == 1) {
            memo[i][j] = grid[i][j] + grid[0][0];
        } else if (j==0&&i == 1) {
            memo[i][j] = grid[0][0] + grid[i][j];
        }

        if (i > 0 && j > 0) {
            memo[i][j] = Math.min(fibPath(memo, grid, i, j - 1), fibPath(memo, grid, i - 1, j)) + grid[i][j];
        } else if (i > 0 && j == 0) {
            memo[i][j] = fibPath(memo, grid, i - 1, j) + grid[i][j];
        } else if (j > 0 && i == 0) {
            memo[i][j] = fibPath(memo, grid, i, j - 1) + grid[i][j];
        }

        return memo[i][j];
    }
}

实现思路:

动态规划:自底向上。

实现:

开辟二维数组存储:

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] memo = new int[m][n];
        memo[0][0] = grid[0][0];
        int i,j;
        for(i=1;i<n;i++){
            memo[0][i]=memo[0][i-1]+grid[0][i];
        }
        for(i=1;i<m;i++){
            memo[i][0]=memo[i-1][0]+grid[i][0];
        }

        for(i=1;i<m;i++){
            for(j=1;j<n;j++){
                memo[i][j]=Math.min(memo[i][j-1],memo[i-1][j])+grid[i][j];
            }
        }
        return memo[m-1][n-1];
    }
}

开辟一维数组存储:

1 3 1
1 5 1
4 2 1
-----------
1 4 5
2 7 6
6 8 7

实际上用一维数组把巧妙的保存了当前(i,j)位置对应的上一次(i-1,j)与更新后的(i,j-1)的值。

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] memo = new int[n];
        memo[0] = grid[0][0];
        int i,j;
        for(i=1;i<n;i++){
            memo[i]=memo[i-1]+grid[0][i];
        }

        for(i=1;i<m;i++){
            for(j=0;j<n;j++){
                if(j==0){
                    memo[j]+=grid[i][j]; //巧妙的对边界进行相加!
                }else{
                    memo[j]=Math.min(memo[j-1],memo[j])+grid[i][j];
                }
            }
        }
        return memo[n-1];
    }
}

3.120. 三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如,给定三角形:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

说明:

如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

实现思路:

递归

实现:

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return fibTri(triangle,0,0,0);
    }
    public int fibTri(List<List<Integer>> triangle,int row,int col,int min_sum){
        if(row>=triangle.size()){
            return min_sum;
        }
        min_sum+=triangle.get(row).get(col);
        return Math.min(fibTri(triangle,row+1,col,min_sum),fibTri(triangle,row+1,col+1,min_sum));
    }
}

记忆化搜索+递归

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return helper(triangle, 0, 0, new HashSet<>());
    }
    public int helper(List<List<Integer>> triangle, int x, int y, Set<String> visited) {
        //递归终止条件
        if (x == triangle.size()) {
            return 0;
        }
        //使用记忆化搜索的条件
        if (visited.contains(x + " " + y)) {
            return triangle.get(x).get(y);
        }
        int left = helper(triangle, x + 1, y, visited);
        int right = helper(triangle, x + 1, y + 1, visited);
        int sum = Math.min(left, right) + triangle.get(x).get(y);
        triangle.get(x).set(y, sum);
        visited.add(x + " " + y);
        return sum;
    }
}

使用了二维数组空间的动态规划!

直接为tmp多分配一行一列数据,那么就可以不用事先对tmp赋值。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
       int n = triangle.size();
        int[][] tmp = new int[n+1][n+1];
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<=i;j++){
                tmp[i][j]=Math.min(tmp[i+1][j],tmp[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return tmp[0][0];
    }

}

使用了一维数组空间的动态规划!

每次使用一个数组来存储上一次的运算结果。自底向上动态规划。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int rows = triangle.size();
        //定义一维数组存放最近一行数据。
        int[] arr = new int[rows];
        //初始化最底层
        for(int i=0;i<rows;i++){
            arr[i]=triangle.get(rows-1).get(i); //将最后一行数据转存到arr数组。
        }
        for(int i=rows-2;i>=0;i--){
            for(int j=0;j<=i;j++){ //刚好是第几行就有几列数据
                arr[j]=Math.min(arr[j],arr[j+1])+triangle.get(i).get(j);
            }
        }
        return arr[0];
    }
}

上述第一个循环其实可以省去,怎么省去?

直接为arr多分配一列数据空间,保证不溢出。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int rows = triangle.size();
        //定义一维数组存放最近一行数据。
        int[] arr = new int[rows+1];
        for(int i=rows-1;i>=0;i--){
            for(int j=0;j<=i;j++){ //刚好是第几行就有几列数据
                arr[j]=Math.min(arr[j],arr[j+1])+triangle.get(i).get(j);
            }
        }
        return arr[0];
    }
}

不用自定义空间的两种动态规划!

实现思路:

自底向上动态规划。每次挑选当前对应的下一行的左边与右边元素中最小元素,然后依次原地累加,直到最后累加到第一行就是最后结果。

实现:

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {

        for(int i=triangle.size()-2;i>=0;i--){
            for(int j=0;j<triangle.get(i).size();j++){
                triangle.get(i).set(j,triangle.get(i).get(j)+Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j+1)));
            }
        }
        return triangle.get(0).get(0);
    }
}

实现思路:

自顶向下动态规划。分为三种情况,左边界、中间、右边界。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if (j == 0) 
                    //当前行(i,j)与上一行(i-1,j)相关
                    //将当前行(i,j)对应的值设置为当前行(i,j)的值加上上一行(i-1,j)对应的值。
                    triangle.get(i).set(j, triangle.get(i-1).get(j) + triangle.get(i).get(j));
                else if (j == triangle.get(i).size()-1)
                    //当前行(i,j)与上一行(i-1,j-1)相关
                    //将当前行(i,j)对应的值设置为当前行(i,j)的值加上上一行(i-1,j-1)对应的值。
                    triangle.get(i).set(j, triangle.get(i-1).get(j-1) + triangle.get(i).get(j));
                else
                    //中间部分与上一行的(i-1,j)、(i-1,j-1)相关。
                    triangle.get(i).set(j, Math.min(triangle.get(i-1).get(j-1), triangle.get(i-1).get(j)) 
                    + triangle.get(i).get(j));
            }
        }
        return Collections.min(triangle.get(triangle.size()-1)); //取出最后一行的最小值即可。
    }

}

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode周赛194总结

    这次来参加了一下194周赛,做完前两道,后面第三道思路不太对,写错了,就差了一个函数调用。。最后一道是一个prim/kruskal算法求解最小生成树的问题,这两...

    公众号guangcity
  • BFS+DFS终结游戏题目

    题目描述:在一个 2 x 3 的板上(board)有 5 块砖瓦,用数字 1~5 来表示, 以及一块空缺用 0 来表示.

    公众号guangcity
  • 现代C++之constexpr

    (1)C++11中的constexpr指定的函数返回值和参数必须要保证是字面值,而且必须只有一行return代码,这给函数的设计者带来了更多的限制,比如通常只能...

    公众号guangcity
  • BZOJ4260: Codechef REBXOR (01Tire树)

    attack
  • Java 8 中的拉姆达表达式是什么?

    拉姆达表达式就是一个匿名函数。在 C#中,拉姆达表达式是一个委托类型,因此拉姆达表达式可以赋值给一个委托变量。 Java 中,没有委托,Java 的设计者只能...

    水货程序员
  • Poj 1564 || HDU 1258 Sum It Up(dfs+技巧)

          题意就是先输入n,m,然后输入m个数,问在这m个数里有多少种任意相加起来等于n的方法,并且输出这些相加的数。

    Ch_Zaqdt
  • PAT(乙级)1013

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.net/z...

    zy010101
  • 2019HDU多校赛第二场 HDU 6601 Keen On Everything But Triangle( 主席树求区间第k大)

    用户2965768
  • 洛谷P2881 [USACO07MAR]排名的牛Ranking the Cows(bitset Floyd)

    显然如果题目什么都不说的话需要\(\frac{n * (n - 1)}{2}\)个相对关系

    attack
  • 「c++小学期」实验题目及代码

    面向对象编程的C++,和平时做题用的C++还是有差距的。实验的题目都是小题目,就都做一下吧。

    饶文津

扫码关注云+社区

领取腾讯云代金券