第三章总结
- 请写出作业“算法第三章3”中题目“7-4 最低通行费”的动态规划方程
请按照如下格式书写动态规划方程：
（1）状态表示：
（2）状态方程：
（3）边界条件：
（4）时间、空间复杂度分析
动态规划方程：
（1）状态表示：
设 dp[i][j] 表示从左上角 (0, 0) 到达网格中 (i, j) 位置的最小费用。
（2）状态方程：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1], dp[i+1][j] (if i < N-1), dp[i][j+1] (if j < N-1))
其中，grid[i][j] 表示网格中 (i, j) 位置的费用。注意，由于不能越界，所以在考虑 dp[i+1][j] 和 dp[i][j+1] 时需要判断索引是否小于 N-1。
（3）边界条件：
dp[0][0] = grid[0][0]，因为从起点开始没有额外的费用。
（4）时间、空间复杂度分析：
时间复杂度：O(N^2)，因为我们需要遍历整个网格一次。
空间复杂度：O(N^2)，因为我们需要一个二维数组来存储每个位置的最小费用。
- 结合本章的学习，总结你对动态规划法的体会和思考
体会和思考：
动态规划的核心思想通过将问题分解为更小的子问题，并存储这些子问题的解来避免重复计算，从而显著提高算法的效率，其中每个问题的解都依赖于其子问题的解。动态规划的关键在于如何定义状态以及状态之间的转移关系。在动态规划中，我们需要定义一个或多个状态变量来表示问题的当前状态。而状态转移方程描述了如何从一个或多个先前状态转移到当前状态，并计算出当前状态的最优解。
我觉得动态规划的难点在于如何正确地定义状态和状态转移方程，这通常需要深入理解和分析问题。还要学会识别哪些类型的问题适合用动态规划解决，并能够灵活地定义状态和状态转移方程。但是我又觉得动态规划理解起来还蛮有趣的，看解析理解了题目然后分析问题的时候虽然有点绕，但是理解完觉得很好玩，特别是一些题目列出矩阵然后在读取和输出的时候，列动态方程的时候都比较巧妙，