动态规划n个台阶的走法

陌上人如玉
公子世无双

前言

n 个台阶 一次只能走 一步或者两步，问有多少种走法

问题分析

假设有 n 个台阶：

 当 n=0，即没有台阶时 走法为 0
 当 n=1，台阶为 1 时 走法为 1
 当 n=2，台阶为 2 时 走法为 2：一步一步，两步 

当为 n 个时, 相当于在 n - 1 这个台阶走一步或者在 n - 2 这个台阶走两步
所以 n 个台阶 相当于 n- 1 个台阶的走法加上 n - 2 个台阶的走法

递归实现：

 递归函数：dp(n) = dp(n-1) + dp(n-2)
 递归出口：n=0 return 0
          n=1 return 1
          n=2 return 2
          

如果有对递归思想不是很懂的可以查看我之前发过的递归文章链接描述，相信对你有很大帮助

代码实现

/**
     n 个台阶 一次只能走 一步 l 或者两步，问有多少步解法
     当 n=0，即没有台阶时 走法为 0
     当 n=1，台阶为 1 时 走法为 1
     当 n=2，台阶为 2 时 走法为：一步一步，两步
     
     当为 n 个时, 相当于在 n - 1 这个台阶走一步或者在 n - 2 这个台阶走两步
     所以 n 个台阶 相当于 n- 1 个台阶的走法加上 n - 2 个台阶的走法
     
     递归实现：递归函数：dp(n) = dp(n-1) + dp(n-2)
     递归出口：n=0 return 0、n=1 return 1、n=2 return 2
     @param n 个台阶
     @return n 个台阶走法
     */
    int dp(int n) {if (n == 0) {return 0;} else if (n == 1) {return 1;} else if (n == 2) {return 2;}  else {return dp(n-1) + dp(n-2);
        }
    }

功能测试

    int main(int argc, const char * argv[]) {
        @autoreleasepool {
            int sum;
            sum = dp(2);
            NSLog(@"2 个台阶的走法：%d\n", sum);
            
            sum = dp(3);
            NSLog(@"3 个台阶的走法：%d\n", sum);
            
            sum = dp(4);
            NSLog(@"4 个台阶的走法：%d\n", sum);
            
            sum = dp(9);
            NSLog(@"9 个台阶的走法：%d\n", sum);
        }
        return 0;
    }

源码地址

[链接描述][4]