LeetCode动态规划上之递归+记忆化搜索+DP逐步进阶(上)
- 2019 年 10 月 6 日
- 筆記
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)); //取出最后一行的最小值即可。 } }
