【动态规划】三步问题

**动态规划三步问题**

动态规划是一种强大的算法工具，用于解决复杂的问题。它通过分解问题、建立状态转移方程以及使用记忆化技术来减少计算量，从而提高效率。在本文中，我们将讨论一个经典的动态规划问题——三步问题。

**问题描述**

假设我们有一个3 步长的台阶，需要爬上去。每一步都可以选择向上或向下移动。但是，有一些特殊的台阶，如果向上移动，则会失去一条生命。如果剩余生命为零，则无法继续爬行。

给定一个目标台阶高度，我们需要找到从底部开始爬到顶部所需的最少步数。我们可以选择向上或向下移动，但不能超出台阶范围。

**动态规划解决方案**

为了解决这个问题，我们可以使用动态规划来建立状态转移方程。假设 `f(i)` 表示从底部开始爬到第 `i` 个台阶所需的最少步数。

我们可以根据以下规则建立状态转移方程：

* 如果当前台阶是特殊台阶，则 `f(i) = f(i-1) +2`（向上移动并失去一条生命）
* 否则，`f(i) = min(f(i-1), f(i-2)) +1`（选择最优路径）

我们可以使用记忆化技术来存储已经计算过的状态，从而避免重复计算。

**代码示例**

def climbStairs(n):
 # 初始化记忆化数组 memo = [0] * (n +1)
 # 基础案例 memo[0] =0 memo[1] =1 for i in range(2, n +1):
 # 如果当前台阶是特殊台阶，则向上移动并失去一条生命 if i ==3:
 memo[i] = memo[i-1] +2 else:
 # 否则，选择最优路径 memo[i] = min(memo[i-1], memo[i-2]) +1 return memo[n]