leetcode动态规划

布满荆棘的人生 2022-09-05 04:07 173阅读 0赞

1.  爬楼梯

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

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？  
动态规划模板题，思考方法，1个台阶只有一种走法，2个台阶，可以一次走2个，或者走两次一个有两种。所以如果有n个台阶，先走一个，在考虑剩下n-1个；或者先走两个，在考虑剩下(n-2)个，即f(n)=f(n-1)+f(n-2)。

class Solution {
        
        HashMap<Integer,Integer> map=new HashMap();
        public int climbStairs(int n) {
        
        if(n==1)return 1;
        if(n==2)return 2;
        if(map.containsKey(n)){
        
            return map.get(n);
        }
        int sum=climbStairs(n-1)+climbStairs(n-2);
        map.put(n,sum);
        return sum;
        }
    }

1.  打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

输入：\[1,2,3,1\]  
输出：4  
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。  
偷窃到的最高金额 = 1 + 3 = 4 。

采用dp存储为n时的最高获利数值，只有一家时，dp\[0\]=nums\[0\],有两家的时候，则取两个中的较大值，为n家的时候，分为两种情况，如果取第n个值，则dp\[n\]=dp\[n-2\]+nums\[n\]（//不能连续取）,或者不取第n个,则dp\[n\]=dp\[n-1\]。

class Solution {
        
        public int rob(int[] nums) {
        
        int l=nums.length;
        if(l==0||nums==null){
        return 0;}
        if(l==1){
        return nums[0];}
        int[] dp=new int[l];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<l;i++){
        
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[l-1];
        }
    }

1.  三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。  
输入：triangle = \[\[2\],\[3,4\],\[6,5,7\],\[4,1,8,3\]\]  
输出：11  
解释：如下面简图所示：  
2  
3 4  
6 5 7  
4 1 8 3  
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

建立二维数组nums保存从三角形顶端到(m,n)的最小路径长度，路径向下的过程，每行第一个和最后一个需要特殊处理，等于上一行存储的路线距离加上第一个值，每行最后一个同理，中间的则取较小值。最后在查看nums中最后一行中的最小值返回即可。

class Solution {
        
        public int minimumTotal(List<List<Integer>> triangle) {
        
        int n=triangle.size();
        int[][] nums=new int[n][n];
        nums[0][0]=triangle.get(0).get(0);
        for(int i=1;i<n;i++){
        
            nums[i][0]=nums[i-1][0]+triangle.get(i).get(0);//第一个特判
            for(int j=1;j<i;j++){
        
                nums[i][j]=Math.min(nums[i-1][j]+triangle.get(i).get(j),nums[i-1][j-1]+triangle.get(i).get(j));
            }
            nums[i][i]=nums[i-1][i-1]+triangle.get(i).get(i);//最后一个特判
        }
        int res=nums[n-1][0];
        for(int j=1;j<n;j++){
        
            res=Math.min(res,nums[n-1][j]);
        }
        return res;
        }
    }

1.  不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？  
nums二维数组存储从(0,0)到(m,n)的路线种类，从起始格子到当前格子的路线种类数，等于他上一行的那个格子的种类数加上上一列的那个格子的种类数，首先将第一行和第一列的值都归为1。

class Solution {
        
        public int uniquePaths(int m, int n) {
        
        int[][] nums=new int[m][n];//从0，0到m,n的路线种类数
        for(int i=0;i<m;i++){
        
            nums[i][0]=1;
        }
        for(int j=0;j<n;j++){
        
            nums[0][j]=1;
        }
        for(int i=1;i<m;i++){
        
            for(int j=1;j<n;j++){
        
                nums[i][j]=nums[i-1][j]+nums[i][j-1];
            }
        }
        return nums[m-1][n-1];
        }
    }

1.  不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？  
输入：obstacleGrid = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]  
输出：2  
解释：  
3x3 网格的正中间有一个障碍物。  
从左上角到右下角一共有 2 条不同的路径：

1.  向右 -> 向右 -> 向下 -> 向下
2.  向下 -> 向下 -> 向右 -> 向右

跟上题相比多个障碍物，如果某个格子出现障碍物，则值直接设置为0，如果在第一行或第一列出现障碍物，则要将出现障碍物的点以及其后的所有格，值都设置为0。

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][] nums=new int[m][n];//从0，0到m,n的路线种类数
        int flag=0;
        for(int i=0;i<m;i++){
        
            if(obstacleGrid[i][0]==0&&flag==0)
            {
        nums[i][0]=1;}
            else{
        
                nums[i][0]=0;
                flag=1;
            }
        }
        int flag1=0;
        for(int j=0;j<n;j++){
        
            if(obstacleGrid[0][j]==0&&flag1==0)
            {
        nums[0][j]=1;}
            else{
        
                nums[0][j]=0;
                flag1=1;
            }
        }
        for(int i=1;i<m;i++){
        
            for(int j=1;j<n;j++){
        
                if(obstacleGrid[i][j]==0)
                {
        nums[i][j]=nums[i-1][j]+nums[i][j-1];}
                else{
        
                    nums[i][j]=0;
                }
            }
        }
        return nums[m-1][n-1];
        }
        }

1.  跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。  
输入：nums = \[2,3,1,1,4\]  
输出：true  
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

dp数组存储当前位置能到达的最远位置，dp\[i\]=Math.max(dp\[i-1\],nums\[i\]+i);  
和前一格子相等，或者等于这一格能够跳跃的距离。  
注意特殊取值的判断。

class Solution {
        
        public boolean canJump(int[] nums) {
        
        int l=nums.length;
        if(l==1)return true;
        int[] dp=new int[l];
        int flag=0;
        for(int i=0;i<l;i++){
        
            if(nums[i]==0){
        
                flag=1;
            }
        }
        if(flag==0)return true;
        dp[0]=nums[0];
        if(dp[0]==0)return false;
        if(dp[0]>=l)return true;
        for(int i=1;i<l-1;i++){
        
            dp[i]=Math.max(dp[i-1],nums[i]+i);
            if(dp[i]<=i)return false;
            if(dp[i]>=l-1)return true;
        }
        return false;
        }
    }

1.  跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

此题默认能够跳到结尾，并求最少需要的步数。  
设i为目标点，j为起跳点。  
如果找到了一个num\[j\]+j>=i，则说明j可以跳到i。  
dp数组存储所需要的步数，所以递推公式为dp\[i\]=dp\[j\]+1。

class Solution {
        
        public int jump(int[] nums) {
        
        int l=nums.length;
        int[] dp=new int[l];
        int j=0;
        for(int i=1;i<l;i++){
        
            while(j+nums[j]<i)j++;
            dp[i]=dp[j]+1;
        }
        return dp[l-1];
        }
    }