1.不同路径

1.题目链接


2.算法原理详解

  • 思路
    • 确定状态表示 -> dp[i][j]的含义

      • 走到dp[i][j]的时候,一共有多少种方式
        请添加图片描述
    • 推导状态转移方程

      • dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    • 初始化:dp表多开一行和一列虚拟结点,避免处理边界

      • dp[0][1] = 1 || dp[1][0] = 1
        请添加图片描述
    • 确定填表顺序:从上往下,从左往右

    • 确定返回值:dp[n][m]

  • 上述如果dp表不多开那一行和一列虚拟结点会怎么样?
    • 需要做边界处理,将第一列和第一行先初始化为1

3.代码实现

int uniquePaths(int n, int m) 
{
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    dp[0][1] = 1;

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

    return dp[n][m];
}

2.不同路径 II

1.题目链接


2.算法原理详解

  • 思路
    • 确定状态表示 -> dp[i][j]的含义

      • 走到dp[i][j]的时候,一共有多少种方式
        请添加图片描述
    • 推导状态转移方程

      • dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        请添加图片描述
    • 初始化:dp表多开一行和一列虚拟结点,避免处理边界

      • dp[0][1] = 1 || dp[1][0] = 1
        请添加图片描述
    • 确定填表顺序:从上往下,从左往右

    • 确定返回值:dp[n][m]


3.代码实现

int uniquePathsWithObstacles(vector<vector<int>>& ob) 
{
    int n = ob.size(), m = ob[0].size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    dp[0][1] = 1;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(ob[i - 1][j - 1] == 0) // 注意下表映射关系
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

    return dp[n][m];
}

3.珠宝的最高价值

1.题目链接


2.算法原理详解

  • 思路
    • 确定状态表示 -> dp[i][j]的含义

      • 到达dp[i][j]的时候,此时的最大价值
    • 推导状态转移方程

      • dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1]) + g[i][j]
        请添加图片描述
    • 初始化:dp表多开一行和一列虚拟结点,避免处理边界

      • 第一行和第一列全部初始化为0即可
    • 确定填表顺序:从上往下,从左往右

    • 确定返回值:dp[n][m]


3.代码实现

int jewelleryValue(vector<vector<int>>& frame) 
{
    int n = frame.size(), m = frame[0].size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
        }
    }

    return dp[n][m];
}
Logo

助力广东及东莞地区开发者,代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展,成为松山湖开发者首选的工作与学习平台

更多推荐