【动态规划篇】-阿南达文事网

【动态规划篇】

62. 不同路径

题目链接： 62. 不同路径

题目解析：

状态表示 dp[i][j]表示：以[i][j]为终点时，一共有多少种路径。
状态转移方程 以[i][j]最近的几步来分析问题，要么从[i-1][j]位置向下走一步到达[i][j],要么从[i][j-1]向右走一步到达[i][j]。所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
初始化 为了防止越界，我们就需要初始化下图中红色线画的这部分

这里我们有个小技巧，那就是让dp表多开一行和一列

因为到达[1][1]这个位置共有一种路径，所以我们仅需将dp[1][0]或者dp[0][1]位置初始化为1，其余位置初始化为0即可。

填表顺序 从上向下，从左向右
返回值因为dp[i][j]表示到达[i][j]位置时，一共的路径数，我们最终要到达[m][n]位置，所以我们返回dp[m][n]即可。

代码实现：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int uniquePaths(int m, int n) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回结果
        vector<vector<int>> dp(m + 1,vector<int>(n + 1));
        dp[1][0] = 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][n];
    }
};

时间复杂度：O(m*n) 空间复杂度：O(m*n)

63. 不同路径II

题目链接： 63. 不同路径II

题目解析： 这道题和上面那道题极度的相似，只不过是加了个障碍物

状态表示 dp[i][j]表示：以[i][j]为终点时，一共有多少种路径。
状态转移方程 以距离[i][j]最近的一步来划分问题，划分为[i][j]上一步有障碍物时和没有障碍物时。当有障碍物时那么此时的路径就到达不了[i][j]，所以到达[i][j]的总的方法数就为0，当没有障碍物时，此时的问题就和上面那道题的思路就一摸一样了要么从[i-1][j]位置向下走一步到达[i][j],要么从[i][j-1]向右走一步到达[i][j]。所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
初始化 因为到达[1][1]这个位置共有一种路径，所以我们仅需将dp[1][0]或者dp[0][1]位置初始化为1，其余位置初始化为0即可。
填表顺序 从上向下，从左向右
返回值 因为dp[i][j]表示到达[i][j]位置时，一共的路径数，我们最终要到达[m][n]位置，所以我们返回dp[m][n]即可。

代码实现：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        //1. 创建dp表   
        //2. 初始化
        //3. 填表
        //4. 返回结果
        int m = ob.size(),n = ob[0].size();
        vector<vector<int>> dp(m + 1,vector<int> (n + 1));
        dp[0][1] = 1;
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
                if(ob[i - 1][j - 1] == 0) //这里需要特别注意一下下标的映射关系
                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

        return dp[m][n];
    }
};

时间复杂度：O(m*n) 空间复杂度：O(m*n)

LCR 166. 珠宝的最高价值

题目链接： LCR 166. 珠宝的最高价值

题目解析：

状态表示 dp[i][j]表示：以[i][j]为终点时，获得的珠宝的最高价值
状态转移方程 以最近的一步来划分问题，要么从[i-1][j]位置走一步到达[i][j],要么从[i-1][j]位置走一步到达[i][j]，此时珠宝的最高价值就是dp[i-1][j]和dp[i][j-1]两者大的一个加上[i][j]位置珠宝的价值。所以dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + frame[i][j]，这里要注意下标的映射关系，所以此时的frame[i][j]应该是frame[i-1][j-1]，因为数组整体向右下角移动了一位。
初始化 这道题我们申请dp表时也多开出一行和一列，为了不影响其余位置的值，我们将这一行和这一列初始化成0即可。
填表顺序 从上往下，自左向右
返回值 因为dp[i][j]表示以[i][j]为终点时，获得的珠宝的最高价值，我们最终要到达右下角，记二维数组的宽为m宽为n，所以返回dp[m][n]

代码实现：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(),n = frame[0].size();
        //1.创建dp表
        vector<vector<int>> dp(m + 1 ,vector<int> (n + 1));
        //2.初始化
        //因为vector创建的数组默认初始化为0，所以这里不用做处理
        //3.填表
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
                dp[i][j] = max(dp[i][j-1],dp[i-1][j]) + frame[i-1][j-1];
        return dp[m][n];
    }
};

时间复杂度：O(m*n) 空间复杂度：O(m*n)

931. 下降路径最小和

题目链接： 931. 下降路径最小和

题目解析：

状态表示 dp[i][j]表示：到达[i][j]位置时的最小下降路径
状态转移方程 以最近的一步来划分问题

要到达[i][j]位置，要么从1位置到达[i][j],要么从2位置到达[i][j],要么从3位置到达[i][j]

dp[i][j] = min(dp[i-1][j-1],min(do[i-1][j],dp[i-1][j+1])) + matrix[i][j]

初始化 为了保证填表的时候不越界，所以我们在创建dp表的时候多开一行，多开两列。为了保证虚拟节点里面的值不影响填表，所以我们在初始化的时候将dp表里面的值都初始化为+∞，将第一行初始化为0即可。

填表顺序 从上往下
返回值 由于最后要求的是下降路径的和最小，dp[i][j]表示的是到达[i][j]位置时的和最小，所以我们返回最后一行的最小值即可

代码实现：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        //1.创建dp表
        int n = matrix.size();
        vector<vector<int>> dp(n+1,vector<int>(n + 2,INT_MAX));
        //2.初始化
        for(int i = 0;i <= n;i++) dp[0][i] = 0;
        //3.填表
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1])) + matrix[i-1][j-1];

        int ret = INT_MAX;
        for(int i = 0;i <= n;i++) ret = min(ret,dp[n][i]);
        return ret;
                
    }
};

时间复杂度：O(n²) 空间复杂度：O(n²)

64. 最小路径和

题目链接： 64. 最小路径和

题目解析：

状态表示 dp[i][j]表示：到达[i][j]位置时的数字最小和
状态转移方程 以最近的一步来分析问题，到达[i][j]位置，要么从[i][j-1]位置向右走一步到达[i][j],要么从[i-1][j]位置向下走一步到达[i][j]。要求到达[i][j]位置数字最小和只需求得到达[i][j-1]位置数字最小和在加上[i][j]位置上的数字与[i-1][j]位置数字最小和在加上[i][j]位置上的数字的小的那一个。所以dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j]

【动态规划篇】