Day38——Dp专题

怼烎@ 2024-03-31 12:42 70阅读 0赞

## DP专题 ##

##### 动态规划五部曲： #####

*  确定dp数组以及下标的含义
 *  确定递推公式
 *  dp数组如何初始化
 *  确定遍历顺序
 *  举例推导dp数组

#### 1.斐波那契数 ####

题目链接：[509. 斐波那契数 - 力扣（LeetCode）][509. _ - _LeetCode]

**思路**：做dp类题目，根据dp五部曲来的思路来解决，dp五部曲可以贯彻整个dp专题。

*  **确定dp数组以及下标的含义**

dp\[i\]的定义为：第i个数的斐波那契数值是dp\[i\]

*  **确定递推公式**

状态转移方程 dp\[i\] = dp\[i - 1\] + dp\[i - 2\];

*  **dp数组如何初始化**

题目中把如何初始化也直接给我们了，如下：

dp[0] = 0;
    dp[1] = 1;

*  **确定遍历顺序**

dp\[i\]是依赖 dp\[i - 1\] 和 dp\[i - 2\]，那么遍历的顺序一定是从前到后遍历的

*  **举例推导dp数组**

**Code**

递归法：

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

动态规划：

**压缩版本**

class Solution {
        
        public int fib(int n) {
        
            if(n < 2) return n;
            int a = 0,b = 1,sum = 0;
            for(int i = 1;i < n;i++){
        
                sum = a + b;
                a = b;
                b = sum;
            }
            return sum;
        }
    }

**非压缩版本**

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

#### 2. 爬楼梯 - 力扣 ####

题目链接：[70. 爬楼梯 - 力扣（LeetCode）][70. _ - _LeetCode]

思路：与上一道题目思路类似

**Code**

动态规划:

**非压缩版本**

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

**压缩版本**：

class Solution {
        
        public int climbStairs(int n) {
        
            if(n<=2) return n;
            int a = 1,b = 2,num = 0;
            for(int i = 3;i <= n;i++){
        
                num = a + b;
                a = b;
                b = num;
            }
            return num;
        }
    }

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

**思路**：

**递归五部曲**：

*  **确定dp数组以及下标的含义**

dp\[i\]的定义：到达第i台阶所花费的最少体力为dp\[i\]。

*  **确定递推公式**

\*\***可以有两个途径得到dp\[i\]，一个是dp\[i-1\] 一个是dp\[i-2\]。**

dp\[i - 1\] 跳到 dp\[i\] 需要花费 dp\[i - 1\] + cost\[i - 1\]。

dp\[i - 2\] 跳到 dp\[i\] 需要花费 dp\[i - 2\] + cost\[i - 2\]。

*  **dp数组如何初始化**

初始化 dp\[0\] = 0，dp\[1\] = 0;

*  **确定遍历顺序**

dp\[i\]由dp\[i-1\]dp\[i-2\]推出，所以是从前到后遍历cost数组

*  **举例推导dp数组**

![image-20221128113005287][]

**Code**

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

#### 4. 不同路径 ####

题目链接：[62. 不同路径 - 力扣（LeetCode）][62. _ - _LeetCode]

思路：

*  **确定dp数组以及下标的含义**

dp\[i\]\[j\] ：表示从（0 ，0）出发，到(i, j) 有dp\[i\]\[j\]条不同的路径。

*  **确定递推公式**

dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - 1\]，因为dp\[i\]\[j\]只有这两个方向过来

*  **dp数组如何初始化**

如何初始化呢，首先dp\[i\]\[0\]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp\[0\]\[j\]也同理。

所以初始化代码为：

for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;

*  **确定遍历顺序**

从左到右，从上到下

*  **举例推导dp数组**

![image-20221128121119106][]

**Code**

动态规划：

class Solution {
        
        public int uniquePaths(int m, int n) {
        
            int[][] dp = new int[m][n];
            for(int i = 0;i < m;i++) dp[i][0] = 1;
            for(int j = 0;j < n;j++) dp[0][j] = 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];
        }
    }

#### 5.不同路径 II ####

题目链接：[63. 不同路径 II - 力扣（LeetCode）][63. _ II - _LeetCode]

这一题和上一题的区别是，本题多了障碍物！

题目链接：[980. 不同路径 III - 力扣（LeetCode）][980. _ III - _LeetCode]

思路：

*  **确定dp数组以及下标的含义**

dp\[i\]\[j\] ：表示从（0 ，0）出发，到(i, j) 有dp\[i\]\[j\]条不同的路径。

*  **确定递推公式**

dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - 1\]，因为dp\[i\]\[j\]只有这两个方向过来

if (obstacleGrid[i][j] == 0) {
         // 当(i, j)没有障碍的时候，再推导dp[i][j]
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }

*  **dp数组如何初始化**

![image-20221128121628055][]

如何初始化呢，首先dp\[i\]\[0\]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp\[0\]\[j\]也同理。

所以初始化代码为：

for(int i = 0; i < n && obstacleGrid[0][i] == 0; i ++) f[0][i] = 1;
    // 当遇到障碍物时循环就会结束了！
    for(int i = 0; i < m && obstacleGrid[0][i] == 0; i ++) f[i][0] = 1;

**注意代码里for循环的终止条件，一旦遇到obstacleGrid\[i\]\[0\] == 1的情况就停止dp\[i\]\[0\]的赋值1的操作，dp\[0\]\[j\]同理**

*  **确定遍历顺序**

从左到右，从上到下

for (int i = 1; i < m; i++) {
        
        for (int j = 1; j < n; j++) {
        
            if (obstacleGrid[i][j] == 1) continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

*  **举例推导dp数组**

有障碍物的为1

![image-20221128121847385][]

**Code**

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
    
            //如果在起点或终点出现了障碍，直接返回0
            if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
        
                return 0;
            }
    
            for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
        
                dp[i][0] = 1;
            }
            for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
        
                dp[0][j] = 1;
            }
    
            for (int i = 1; i < m; i++) {
        
                for (int j = 1; j < n; j++) {
        
                    dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
                }
            }
            return dp[m - 1][n - 1];
        }
    }

[509. _ - _LeetCode]: https://leetcode.cn/problems/fibonacci-number/
[70. _ - _LeetCode]: https://leetcode.cn/problems/climbing-stairs/
[image-20221128113005287]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1532176df0fb465093e39a6822823bfc.png
[62. _ - _LeetCode]: https://leetcode.cn/problems/unique-paths/
[image-20221128121119106]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/071a211a7bb4438ab0b8f5f1b74ee787.png
[63. _ II - _LeetCode]: https://leetcode.cn/problems/unique-paths-ii/
[980. _ III - _LeetCode]: https://leetcode.cn/problems/unique-paths-iii/
[image-20221128121628055]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/9296982622574d2ba0229875d49daf8e.png
[image-20221128121847385]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/efbdc88cef154a098d97bec80474bb97.png