[Algorithm][动态规划][路径问题][不同路径][不同路径Ⅱ][珠宝的最高价值]详细讲解

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.题目链接

• 不同路径 II

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];
}