本文共 1089 字，大约阅读时间需要 3 分钟。

Objective-C 实现爬楼梯问题的动态规划算法

爬楼梯问题是一个经典的动态规划问题，描述如下：假设你正在爬楼梯，楼梯有 n 级台阶，每次你可以爬 1 级或 2 级台阶，问你有多少种不同的方法可以爬到楼顶。

动态规划解决方法

这个问题可以通过动态规划来解决。动态规划的基本思想是将问题分解成更小的子问题，并通过记录子问题的解来解决整个问题。

我们可以定义一个数组 dp，其中 dp[i] 表示到达第 i 个台阶的方法数。由于每次可以爬 1 级或 2 级台阶，所以我们有递推关系：

• dp[i] = dp[i-1] + dp[i-2]

这个递推关系说明，到达第 i 个台阶的方法数等于到达第 i-1 个台阶的方法数加上到达第 i-2 个台阶的方法数。

初始条件

• dp[0] = 1：如果没有台阶，到达顶部的方法数是 1（即站在地面）。
• dp[1] = 1：如果只有一个台阶，到达顶部的方法数是 1。

递推公式

对于 i >= 2，我们有：

dp[i] = dp[i-1] + dp[i-2]

代码实现

以下是用 Objective-C 实现的爬楼梯问题的算法：

NSInteger climbStairs(NSInteger n) {    if (n == 0) return 1;    if (n == 1) return 1;        NSInteger dp[] = {1, 1};    for (NSInteger i = 2; i <= n; i++) {        dp[i] = dp[i-1] + dp[i-2];    }    return dp[n];}

代码解释

示例

假设 n = 3，我们可以手动计算：

• dp[0] = 1
• dp[1] = 1
• dp[2] = dp[1] + dp[0] = 1 + 1 = 2
• dp[3] = dp[2] + dp[1] = 2 + 1 = 3

所以，爬到第 3 个台阶的方法数是 3 种。

总结

通过上述方法，我们可以高效地解决爬楼梯问题。动态规划的时间复杂度为 O(n)，空间复杂度为 O(n)。如果需要优化空间复杂度，可以使用只 O(1) 的空间来实现，通过利用三个变量来记录前三个数值。

转载地址：http://zjnfk.baihongyu.com/