动态规划求解最优路径

动态规划可以用来解决一类具有最优子结构的问题，其中最优子结构指的是问题的最优解可以通过子问题的最优解来构造。动态规划的一般思考过程如下：

1. 确定问题的状态：将原问题划分为若干个子问题，并定义每个子问题的状态。

2. 定义状态转移方程：根据子问题之间的关系，确定状态之间的转移方式。

3. 确定初始条件：确定最简单的子问题的解，即初始状态。

4. 确定计算顺序：根据状态转移方程，确定计算状态的顺序，通常是从初始状态开始，按照某种顺序计算其他状态。

5. 计算最优解：根据计算顺序，依次计算每个状态的值，直到计算出最终的目标状态的值。

动态规划与分治、回溯、贪心算法有以下区别和联系：

- 区别：
- 分治算法将问题划分为若干个子问题，然后分别求解子问题，最后将子问题的解合并得到原问题的解。而动态规划则是通过求解子问题的最优解来构造原问题的最优解。
- 回溯算法通过不断回溯和尝试所有可能的解来求解问题，而动态规划则是通过存储已经计算过的子问题的解来避免重复计算，提高效率。
- 贪心算法每次都选择当前看起来最优的解，而不考虑全局最优解。而动态规划则是通过计算每个状态的值来确定最优解。

- 联系：
- 动态规划和分治算法都是将问题划分为若干个子问题，并通过求解子问题的解来构造原问题的解。
- 动态规划和回溯算法都可以用于求解具有最优子结构的问题，但动态规划通过存储已经计算过的子问题的解来避免重复计算，提高效率。

以下是一个使用动态规划求解最优路径的示例：

假设有一个网格，每个格子上都有一个非负整数代表该格子的权值，从左上角出发，每次只能向右或向下移动一格，求从左上角到右下角的路径，使得路径上的权值之和最小。

def minPathSum(grid):
    m = len(grid)
    n = len(grid[0])
    
    # 初始化dp数组
    dp = [[0] * n for _ in range(m)]
    
    # 计算第一行和第一列的最小路径和
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # 计算其他位置的最小路径和
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    
    return dp[m-1][n-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(minPathSum(grid))  # 输出：7