动态规划算法----路径问题

引言

动态规划（Dynamic Programming，简称 DP）是解决复杂问题的一种常用算法思想，在路径模型问题中尤为常见。本文将详细讲解动态规划在路径问题中的应用，包括基本概念、常见题型以及代码实现，帮助读者深入理解这一模型。

什么是路径模型？

路径模型是动态规划的一类经典问题，通常目标是通过某种规则，从起点到达终点，并在路径上累积收益（如最小代价或最大价值）。典型特点包括：

• 阶段性：问题可分解为多个阶段（如路径中的每一格）。
• 状态转移：从一个阶段的状态可以推导出下一个阶段的状态。
• 最优子结构：局部最优解能够决定整体最优解。

常见路径模型问题

算法思路

动态规划求解路径模型问题的核心步骤如下：

1. 定义状态：用 dp[i][j] 表示从起点到达位置 (i, j) 时的某种值（路径数、路径和、最短距离等）。
2. 状态转移方程：根据问题的具体规则，推导 dp[i][j] 的递推关系。
3. 初始化：根据起点或边界条件，设定初始状态。
4. 填表顺序：保证填写当前位置的值所需要的其他值已经计算出。
5. 结果输出：通常为 dp 数组的某个元素，如 dp[m][n] 表示终点的值。

 案例一：不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

这是一个经典的动态规划问题，目标是求机器人从网格左上角到右下角有多少种不同的路径。

算法思路

• 1. 状态定义：用 dp[i][j] 表示从起点到达网格位置 (i, j) 的不同路径数。

• 2. 状态转移方程：对于位置 (i, j)，机器人只能从上方 (i-1, j) 或左侧 (i, j-1) 到达。    所以有  dp[i][j] = dp[i-1][j] + dp[i][j-1]。

• 3. 初始化：第一行和第一列的路径数都为 1，因为机器人只能沿着边缘移动。                       所以有 dp[i][0] = 1 （只能向下），dp[0][j] = 1 （只能向右）。但是这种初始化方式需要使用两个循环来完成。可以使用以下方法将初始化操作放在循环条件里来完成。可以在dp数组的最上边及一行，最左边加一列。方法如下图所示：

只需要将虚拟节点中的dp[0][1]初始化为1，即可将原始dp组完成初始化。

但是要注意虚拟节点的值保证后面的填表正确，还要注意新dp数组和原始数组的下标映射关系。、

4.填表顺序：每一行从左向右填表，每一列从上向下。

5.结果输出：最终的结果为 dp[m][n]，表示从起点到右下角的路径总数。

编写代码

优化：空间复杂度 O(n)

由于 dp[i][j] 只依赖于当前行和上一行的状态，可以用一维数组优化空间复杂度。

优化代码：

int uniquePaths(int m, int n) {
    vector<int> dp(n, 1); // 初始化第一行路径数为 1
    
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[j] += dp[j-1]; // 更新当前列的路径数
        }
    }
    
    return dp[n-1];
}

总结

• 时间复杂度：O(m * n)，需要遍历整个网格。
• 空间复杂度：
  • 二维 DP：O(m * n)
  • 一维优化：O(n)

案例二：不同路径Ⅱ 

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。返回机器人能够到达右下角的不同路径数量。

算法思路

1. 状态表示 定义 dp[i][j] 表示从起点到达 (i, j) 位置的不同路径数。

2. 状态转移方程  对于dp[i][j]可以分为以下两种情况

① 当grid[i][j]位置有障碍物时，则dp[i][j]=0

②当grid[i][j]位置没有障碍物时，则dp[i][j] 的值是从上面或者左边的位置来的路径数之和： dp[i][j] = dp[i-1][j] + dp[i][j-1]，表示从上方或左方到达该点的路径数。

3. 初始化  保证填表时不越界

初始化方法和上道题类似，在最上方加一行，最左边加一行即可，未添加之前有dp[0][j] = 1,   dp[i][0] = 1,要保证这些位置的值正确，只需将添加一行一列之后的新dp[0][1]或者dp[1][0]初始化为1 即可。

但要注意新dp表与原始矩阵的下标映射关系，即dp表的[i，j] 对应grid矩阵的[ i-1,j-1]。

4. 填表顺序    从左向右，从上向下

5.返回值   

因为新增加了一行一列，所以返回值是dp[m][n]

编写代码

int uniquePathsWithObstacles(vector<vector<int>>& grid) {

        int m = grid.size(),n = grid[0].size();
        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++)
            {
                if(grid[i-1][j-1] == 0)   //注意下标的映射关系，dp表的[i，j]对应grid矩阵的[i-1,j-1]
                {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    

        
    }

时间复杂度

• 时间复杂度是 O(m * n)，其中 m 和 n 分别是网格的行数和列数，因为我们需要遍历整个网格。
• 空间复杂度也是 O(m * n)，用于存储 dp 数组。