### 宝宝抢糖果问题的Python实现 根据问题描述，宝宝抢糖果的方式有两种：手快抢 2 个或手慢抢 1 个。因此，统计 N 个糖果可以有多少种分配方式的问题可以转化为一个动态规划问题。每一步的选择取决于前一步的状态，类似于斐波那契数列的递推关系。 以下是基于 Python 的实现代码： ```python def count_ways(n): if n == 0: return 1 # 没有糖果时，只有一种分配方式（什么都不做） if n < 0: return 0 # 糖果数量为负时不合法 dp = [0] * (n + 1) dp[0] = 1 # 初始化：没有糖果时，分配方式为1 if n >= 1: dp[1] = 1 # 初始化：1个糖果时，只有1种分配方式 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] # 当前状态由前两种状态决定 return dp[n] # 测试代码 if __name__ == "__main__": n = int(input("请输入糖果的数量: ")) print(f"分配 {n} 个糖果的方式总数为: {count_ways(n)}") ``` #### 动态规划的核心思想 上述代码使用了动态规划的思想来解决问题。定义 `dp[i]` 表示当有 `i` 个糖果时的分配方式总数。状态转移方程如下： - 如果当前宝宝选择抢 1 个糖果，则剩余 `i-1` 个糖果，对应的分配方式为 `dp[i-1]`[^1]。 - 如果当前宝宝选择抢 2 个糖果，则剩余 `i-2` 个糖果，对应的分配方式为 `dp[i-2]`。 因此，状态转移方程为： \[ dp[i] = dp[i-1] + dp[i-2] \] #### 边界条件 - 当 `n=0` 时，表示没有糖果需要分配，此时只有一种分配方式，即什么都不做[^1]。 - 当 `n=1` 时，表示只有一个糖果，此时也只有一种分配方式[^1]。 #### 时间与空间复杂度分析 - 时间复杂度：O(n)，因为需要遍历从 2 到 n 的所有状态。 - 空间复杂度：O(n)，由于使用了一个长度为 n+1 的数组存储中间结果。 如果希望进一步优化空间复杂度，可以通过仅保留最近两个状态的方式来减少内存消耗。以下是优化后的版本： ```python def count_ways_optimized(n): if n == 0: return 1 if n == 1: return 1 prev2, prev1 = 1, 1 # 初始化 dp[0] 和 dp[1] for i in range(2, n + 1): current = prev1 + prev2 # 当前状态等于前两种状态之和 prev2 = prev1 prev1 = current return prev1 # 测试代码 if __name__ == "__main__": n = int(input("请输入糖果的数量: ")) print(f"分配 {n} 个糖果的方式总数为: {count_ways_optimized(n)}") ``` 此版本的时间复杂度仍为 O(n)，但空间复杂度降低为 O(1)。 ---