关键概念回顾
Coddy 动态规划入门 课程的第 14 课，共 15 课。
在这节课中，我们将回顾《动态规划入门》课程中讲解的核心概念。
- 动态规划：动态规划是一种解决优化问题的技术。它将问题拆分为更简单的子问题，并且只求解每个子问题一次。
- 记忆化：记忆化是一种避免重复计算的技术。它会存储开销较大的函数调用的结果，并在相同输入再次出现时返回缓存的结果。
- 制表法：制表法是一种解决动态规划问题的技术。它通过迭代填充存有解的表格或数组，逐步构建出最终答案。
- 最优子结构：如果一个问题的最优解中包含其子问题的最优解，那么这个问题就具有最优子结构。
- 重叠子问题：如果一个问题可以拆分为共享子子问题的子问题，那么这个问题就具有重叠子问题。
- 空间优化：空间优化是一种降低动态规划算法内存需求的技术，只跟踪必要的状态。
- 位掩码：位掩码是一种使用位操作将一组元素表示为二进制数的技术。
- 剪枝：剪枝是一种减少动态规划算法所需计算量的技术，通过避免不必要的计算来实现。
挑战
中等复习挑战：最小成本路径
给你一个 n x n 的网格，用来表示城市地图。网格中的每个单元格都表示一个街道路口，单元格中的值表示经过该路口的成本。你要从网格的左上角走到右下角，并且在每个路口只能向下或向右移动。
编写一个函数 min_cost_path(grid)，将网格作为输入，并返回从左上角到右下角经过网格的最小成本。
例如：
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
min_cost_path(grid) => 7说明：成本最低的路径是 1 -> 3 -> 1 -> 1 -> 1，总成本为 7。
亲手试试
def min_cost_path(grid):
# 在这里编写代码动态规划入门中的所有课
自己练习： Python 在线编译器