动态规划问题汇总(一）

落日映苍穹つ 2024-03-26 12:42 76阅读 0赞

## 基本步骤 ##

![在这里插入图片描述][356825b095094ad29d6f26e69f218ad2.png]

#### 文章目录 ####

*  基本步骤
 *  509. 斐波那契数
 *  70. 爬楼梯
 *  746. 使用最小花费爬楼梯
 *  62.不同路径
 *  63. 不同路径 II
 *  343. 整数拆分
 *  96.不同的二叉搜索树
 *  376. 摆动序列（特殊的自定义二维dp）

## 509. 斐波那契数 ##

![在这里插入图片描述][1d1d12bed7ee44a18ce2c9e376107f16.png]  
递归版本

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

动态规划版本

class Solution {
        
        public int fib(int n) {
        
            int[] dp = new int[n+1];
            if(n<=1){
        
                return n;
            }
            
            dp[0]=0;
            dp[1]=1;
            for(int i=2;i<=n;i++){
        
                dp[i] = dp[i-1]+dp[i-2];
            }
            return dp[n];
        }
    }

优化后，不用存储一整个数组，只需要存储三个数即可

class Solution {
        
        public int fib(int n) {
        
            int[] dp = new int[2];
            if(n<=1){
        
                return n;
            }
            dp[0]=0;
            dp[1]=1;
    
            int sum=0;
            for(int i=2;i<=n;i++){
        
                sum = dp[0]+dp[1];
                dp[0]=dp[1];
                dp[1]=sum;
    
            }
            return sum;
        }
    }

这也是动态规划的常见优化方式，优化额外的存储空间。

## 70. 爬楼梯 ##

![在这里插入图片描述][aa79f40b592f4fdda4c17117f0a5dc0f.png]

class Solution {
        
        public int climbStairs(int n) {
        
            int[] dp = new int[n+1];
            if(n<=1){
        
                return 1;
            }
            dp[1]=1;
            dp[2]=2;
            for(int i=3;i<=n;i++){
        
                dp[i]=dp[i-1]+dp[i-2];
            }
            return dp[n];
    
        }
    }

其实就是斐波那契数列，可自行优化

## 746. 使用最小花费爬楼梯 ##

![在这里插入图片描述][53bbdfbb32154da29be5148046b99741.png]

class Solution {
        
        public int minCostClimbingStairs(int[] cost) {
        
            // dp[i]到达第i个台阶需要支付的最低花费，注意到达该台阶本身并不需花费,即不管cost[i]，只有往上跳了才会产生花费
            int[] dp = new int[cost.length+1];
            if(cost.length==2){
        
                return Math.min(cost[0],cost[1]);
            }
            dp[0]=0;
            dp[1]=0;
            for(int i=2;i<=cost.length;i++){
        
                dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
            }
            return dp[cost.length];
        }
    }

稀里糊涂也写了另一个版本，到达每个台阶的最低花费中，把自身跳的花费也计算了进去，最后到达楼顶的花费，即是倒数第一阶和倒数第二阶的花费最小值。

class Solution {
        
        public int minCostClimbingStairs(int[] cost) {
        
            int[] dp = new int[cost.length];
            if(cost.length==2){
        
                return Math.min(cost[0],cost[1]);
            }
            dp[0]=cost[0];
            dp[1]=cost[1];
            for(int i=2;i<cost.length;i++){
        
                dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];
            }
            return Math.min(dp[cost.length-1],dp[cost.length-2]);
        }
    }

建议直接看前一个版本，更好理解。

## 62.不同路径 ##

![在这里插入图片描述][6428838b22864eef90829308bd0e3555.png]

class Solution {
        
        public int uniquePaths(int m, int n) {
        
        // dp[i][j]表示从(0,0)到(i,j)有多少条不同路径
            int[][] dp = new int[m][n];
            for(int i=0;i<m;i++){
        
                dp[i][0]=1;
            }
            for(int i=0;i<n;i++){
        
                dp[0][i]=1;
            }
            for(int i=1;i<m;i++){
        
                for(int j=1;j<n;j++){
        
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            return dp[m-1][n-1];
        }
    }

优化成两行数组

class Solution {
        
        public int uniquePaths(int m, int n) {
        
            if(m==1 || n==1){
        
                return 1;
            }
            int[][] dp = new int[2][n];
            dp[1][0]=1;
            for(int i=0;i<n;i++){
        
                dp[0][i]=1;
            }
            for(int i=1;i<m;i++){
        
                for(int j=1;j<n;j++){
        
                    dp[1][j] = dp[0][j] + dp[1][j-1];
                    dp[0][j]=dp[1][j];
                    dp[0][j-1] = dp[1][j-1];
                }
            }
            return dp[1][n-1];
        }
    }

进一步优化成一行数组

class Solution {
        
        public int uniquePaths(int m, int n) {
        
            if(m==1 || n==1){
        
                return 1;
            }
            int[] dp = new int[n];
            for(int i=0;i<n;i++){
        
                dp[i]=1;
            }
           
            for(int i=1;i<m;i++){
        
                for(int j=1;j<n;j++){
        
                   dp[j] = dp[j] + dp[j-1];
                }
            }
            return dp[n-1];
        }
    }

**dp\[j\] = dp\[j\] + dp\[j-1\];**  
当你遍历到第j个元素时，当前里面存着的其实是上一次遍历存储的j,即上一行的(i-1,j)，由于是从左到右遍历的，而j-1的元素刚刚更新完，即(i,j-1)，所以直接dp\[j\] = dp\[j\] + dp\[j-1\]即可

## 63. 不同路径 II ##

![在这里插入图片描述][edd6bd8f32b2414c8fe444ac314dad8a.png]

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
    
            // 初始化，若第一行或第一列有障碍物，则后面的路径数皆为0
            for(int i=0;i<m&&obstacleGrid[i][0]==0;i++){
        
                dp[i][0]=1;
            }
            for(int i=0;i<n&&obstacleGrid[0][i]==0;i++){
        
                dp[0][i]=1;
            }
    
            // 从第二行或第二列开始遍历
            for(int i=1;i<m;i++){
        
                for(int j=1;j<n;j++){
        
                    if(obstacleGrid[i][j] == 0){
        
                       dp[i][j]=dp[i-1][j] + dp[i][j-1];
                    }
     
                }
            }
    
            return dp[m-1][n-1];
    
    
        }
    }

直接优化成一维数组

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[] dp = new int[n];
    
            // 如果终点有障碍物，直接返回0
            if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1){
        
                return 0;
            }
    
            // 初始化，有障碍物，则后面的路径数皆为0
            for(int i=0;i<n&&obstacleGrid[0][i]==0;i++){
        
                dp[i]=1;
            }
    
            // dp[0]只需要处理一次，如果第一行第一列无障碍物，则dp[0]为1
            // 后续遍历时，如果其他行第一列有障碍物，则dp[0]=0，而之后的遍历中，dp[0]一直都是0
            // 如果后续第一列无障碍物，则dp[0]=1也一直不会改变
           
            for(int i=1;i<m;i++){
        
                for(int j=0;j<n;j++){
        
                    if(obstacleGrid[i][j] == 1){
        
                        // 如果其他行第一列有障碍物，则dp[0]=0
                       dp[j]=0;
                    }else if(j>0){
        
                         dp[j]=dp[j-1] + dp[j];
                    }
                }
            }
            return dp[n-1];
        }
    }

这里对dp\[0\]的处理有些巧妙。

## 343. 整数拆分 ##

![在这里插入图片描述][ccc2978213304273b7a2a8251c3dde16.png]

class Solution {
        
        public int integerBreak(int n) {
        
            // dp[i]是正整数i可拆分出的最大乘积
            // dp[i] = max{dp[j]*dp[i-j]} j>0且j<i
            // dp[2]=1 dp[3]=2
            int[] dp = new int[n+1];
            dp[2]=1;
            for(int i=3;i<=n;i++){
        
                int sum=0;
                // 后半部分就开始重复了 1x4 2x3 3x2 4x1
                for(int j=1;j<=i/2;j++){
                        
                    sum = Math.max(sum,Math.max(j,dp[j])*Math.max(dp[i-j],i-j));
                }
                dp[i] = sum;
            }
            return dp[n];
        }
    }

其中的Math.max(j,dp\[j\]) 其实直接用j即可，但是我无法理解，所以就没改

## 96.不同的二叉搜索树 ##

![在这里插入图片描述][b4da3fc56e0b485b8f38e15fca7772e0.png]

![在这里插入图片描述][af76a3387f584feea4aa7cc2f46f2461.png]

class Solution {
        
        public int numTrees(int n) {
        
            // gn = g0 * gn-1 + g1 * gn-2
            int[] dp = new int[n+1];
            if(n<=2){
        
                return n;
            }
            dp[0]=1;
            dp[1]=1;
            for(int i=2;i<=n;i++){
        
                for(int j=1;j<=i;j++){
        
                    dp[i] += dp[j-1]*dp[i-j];
                }
            }
    
            return dp[n];
        }
    }

## 376. 摆动序列（特殊的自定义二维dp） ##

![在这里插入图片描述][8898bcc57d1b46429996b05ef1ba4451.png]  
强行用动态规划做了出来，将升序和降序分成两行，拼凑出了dp\[i\]\[j\]

class Solution {
        
        public int wiggleMaxLength(int[] nums) {
        
            // dp[0][i] 到达i元素，以降序为结尾的 摆动序列 的最大长度
            // dp[1][i] 到达i元素，以升序为结尾的 摆动序列 的最大长度
    
            // 到达i元素后，若是升序，可拼凑到降序结尾的摆动序列，即之前降序为结尾的摆动序列最大长度+1，则 dp[1][i] = dp[0][i-1] + 1; dp[0][i]则不变
            // 同理 若是降序 dp[0][i] = dp[1][i-1]+1;dp[1][i]不变
            // 若是相等，全不变
    
            // 初始化，dp[0][0]=1, dp[0][1]=1;
    
            int[][] dp = new int[2][nums.length];
            dp[0][0]=1;
            dp[1][0]=1;
    
            for(int i=1;i<nums.length;i++){
        
    
                // 若是升序
                if(nums[i]>nums[i-1]){
        
                    dp[1][i] = dp[0][i-1] + 1;
                    dp[0][i] = dp[0][i-1];
                }else if(nums[i]<nums[i-1]){
        
                    dp[0][i] = dp[1][i-1]+1;
                    dp[1][i] = dp[1][i-1];
                }else{
        
                    dp[0][i] = dp[0][i-1];
                    dp[1][i] = dp[1][i-1];
                }
            }
    
            return Math.max(dp[0][nums.length-1],dp[1][nums.length-1]);
    
        }
    }

基于此，直接将空间优化，因为只使用到了两个数，定义两个变量即可

class Solution {
        
        public int wiggleMaxLength(int[] nums) {
        
            int up=1;
            int down=1;
            for(int i=1;i<nums.length;i++){
        
                // 若是升序
                if(nums[i]>nums[i-1]){
        
                    up = down + 1;
                }else if(nums[i]<nums[i-1]){
        
                    down=up+1;
                }
            }
            return Math.max(down,up);
        }
    }

[356825b095094ad29d6f26e69f218ad2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c83e8517faaa44cbbeb90f962d977b43.png
[1d1d12bed7ee44a18ce2c9e376107f16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/50b7e550c903485ca701f215eddac251.png
[aa79f40b592f4fdda4c17117f0a5dc0f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d41b4913f5f14d85ad421cb1218249b1.png
[53bbdfbb32154da29be5148046b99741.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/bba046b8de0449f5b5540b5453ace31e.png
[6428838b22864eef90829308bd0e3555.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/214994bf6e524c8b8b897a7302d8f0fe.png
[edd6bd8f32b2414c8fe444ac314dad8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8e7a45b9c92e4021934c31ba284e9827.png
[ccc2978213304273b7a2a8251c3dde16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6be0e92aca4b49018245783fb4fd9bf3.png
[b4da3fc56e0b485b8f38e15fca7772e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/19980eaec7e4438990da9e80818068ff.png
[af76a3387f584feea4aa7cc2f46f2461.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/82fcb598f9da4344b72fd5050fa568fb.png
[8898bcc57d1b46429996b05ef1ba4451.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/baac121f6c374aba802c327b3c876f3b.png