算法训练之动态规划（二）

admin管理员组

文章数量:1440489

算法训练之动态规划（二）

不同路径

不同路径

这个题目需要讨论的是由左上角到右下角的路径总数~我们可以按照动态规划的步骤来进行一步步分析~

1、状态表示

结合这里的题目要求+经验：我们这里的状态表示dp[i][j]到达该位置的路径总数

2、状态转移方程

我们以离【i】【j】位置最近的状态分析状态转移方程 1、到达该位置，可能是从第【i-1】【j】位置向下一步到达的 2、到达该位置，可能是从第【i】【j-1】位置向右一步到达的 所以到达该位置路径数也就是dp[i-1][j]+dp[i][j-1],状态转移方程也就是： dp[i][j]=dp[i-1][j]+dp[i][j-1]

3、初始化

我们可以看到，状态转移方程里面有i-1,j-1当i=0或者j=0的时候显然会出现越界的情况，所以我们需要进行初始化 结合前面如果不想初始化太麻烦，我们可以多申请一些空间，这里与前面不一样的是这里是二维空间，我们前面是一维空间，那么我们这里也就可以多申请一行一列~那么怎么初始化这一行一列呢？ 事实上，增加的这一行一列影响的是原来的第一行第一列，我们就来看看原来的第一行第一列应该是什么值？

因为只能向下或者向右走一步，所以第一行第一列都是1，都只有一种路径，那么应该怎么初始化才能让第一行第一列为1呢？有两种方法： 1、dp[1][0]=1,其他初始化为0 2、dp[0][1]=1 ，其他初始化为0

这两种初始化方式本质上都是让dp[1][1]等于1，有人可能会说那为什么不直接初始化dp[1][1]=1就好了，这是不可以的，因为后面循环会再对dp[1][1]赋值为dp[0][1]+dp[1][0],那么dp[1][1]就等于0，显然结果就不正确了 这种初始化方式还需要注意的是下标的映射关系，这里不是十分明显，我们在后面的题目会分析~

4、填表顺序

我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前向后

5、返回结果

右下角位置的值就是到达右下角路径总数，直接返回dp[m][n]就是我们的结果

代码实现：

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

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

顺利通过~

不同路径Ⅱ

不同路径Ⅱ

这个题目与上一个题目有区别的是多了障碍物，那么我们很容易想到的就是当前位置有障碍物那么肯定到不了当前位置，那么路径数就是0，否则就与我们前面的分析是一样的~

分析：

1、状态表示

结合这里的题目要求+经验：我们这里的状态表示dp[i][j]到达该位置的路径总数

2、状态转移方程

如果当前位置有障碍物，那么路径数就是0，否则我们就以离【i】【j】位置最近的状态分析状态转移方程 1、到达该位置，可能是从第【i-1】【j】位置向下一步到达的 2、到达该位置，可能是从第【i】【j-1】位置向右一步到达的 所以到达该位置路径数也就是dp[i-1][j]+dp[i][j-1],状态转移方程也就是： dp[i][j]=dp[i-1][j]+dp[i][j-1]

3、初始化

我们可以看到，状态转移方程里面有i-1,j-1当i=0或者j=0的时候显然会出现越界的情况，所以我们需要进行初始化 结合前面如果不想初始化太麻烦，我们这里也就可以多申请一行一列~那么怎么初始化这一行一列呢？结合前面一个题目的分析，依然是有两种方法： 1、dp[1][0]=1,其他初始化为0 2、dp[0][1]=1 ，其他初始化为0 这两种初始化方式本质上都是让dp[1][1]等于1~ 这种初始化方式还需要注意的是下标的映射关系，在这个题目中就比较明显了，因为参数是数组，dp的【i】【j】位置是传过来数组的【i-1】【j-1】位置~

4、填表顺序

我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前向后

5、返回结果

右下角位置的值就是到达右下角路径总数，直接返回dp[m][n]就是我们的结果

这个题目与第一个题目没有太大的区别，代码也是十分类似的，我们来实现一下~

代码实现：

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

class Solution 
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob)     
    {
        //1、创建dp表
        int m=ob.size();
        int n=ob[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //2、初始化
        dp[1][0]=1;//a
        //dp[0][1]=1;//b
        //3、填表
        //注意下标映射关系
        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];
                //有障碍物已经被初始化为0
            }
        }
        //4、返回结果
        return dp[m][n];
    }
};

顺利通过~

珠宝的最高价值

珠宝的最高价值

同样利用动态规划的思想来进行一步步分析：

1、状态表示

结合这里的题目要求+经验：我们这里的状态表示dp[i][j]到达该位置拿到的最大珠宝价值

2、状态转移方程

以离【i】【j】位置最近的状态分析状态转移方程 1、到达该位置，可能是从第【i-1】【j】位置向下一步到达的 2、到达该位置，可能是从第【i】【j-1】位置向右一步到达的 但是我们需要的是最大的价值，所以应该是两者之间的最大值加上当前位置的珠宝价值，就是当前位置的最大珠宝价值 状态转移方程也就是：(这里需要注意下标映射关系） dp[i][j]=max（dp[i-1][j]+dp[i][j-1])+frame[i-1][j-1]

3、初始化

我们可以看到，状态转移方程里面有i-1,j-1当i=0或者j=0的时候显然会出现越界的情况，所以我们需要进行初始化 结合前面如果不想初始化太麻烦以及处理边界情况，我们这里也就可以多申请一行一列~那么怎么初始化这一行一列呢？与前面不同的是，这里直接全部初始化为0就好了，因为 dp[i][j]=max（dp[i-1][j]+dp[i][j-1])+frame[i-1][j-1] dp[1][1]会在循环里面等于frame[0][0]~ 这种初始化方式还需要注意的是下标的映射关系，在这个题目中就比较明显了，因为参数是数组，dp的【i】【j】位置是传过来数组的【i-1】【j-1】位置~

4、填表顺序

我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前向后

5、返回结果

直接返回dp[m][n]就是我们的结果

有了前面两个题目的基础，这个题目就比较简单，我们来看看代码实现：

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

class Solution 
{
public:
    int jewelleryValue(vector<vector<int>>& frame) 
    {
        //1、创建dp表
        int m=frame.size();
        int n=frame[0].size();

        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //2、初始化//循环里面会进行初始化
        
        //3、填表
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
                //注意下标映射关系
            }
        }
        //4、返回结果
        return dp[m][n];
    }
};

顺利通过~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-10，如有侵权请联系 cloudcommunity@tencent 删除前往查看int动态规划数组算法dp

本文标签： 算法训练之动态规划（二）