动态规划 - N步台阶问题

阳光穿透心脏的1/2处 2022-12-15 15:27 145阅读 0赞

### 该文转载，因所看文章没有放原文链接，故找不到原文链接 ###

### 题目分析 ###

问题本质：**斐波那契数列**

> 令跳法为f(n)，
> 
> 如果n=1：\{ \{1\}\}，**f(1)=1**；
> 
> 如果n=2：\{ \{1,1\},\{2\}\}，**f(2)=2**；
> 
> 如果n=3，\{ \{1,1,1\}，\{1,2\}，\{2,1\}\}，**f(3)=3**；
> 
> 如果n=6，有两种情况：1)目前在5阶，跳1步到6；2)目前在4阶，跳2步到6。即**f(6)=f(5)+f(4)**；
> 
> ... ...
> 
> 如果有n阶(n>2)，1)目前在n-1阶，跳1步到n；2)目前在n-2阶，跳2步到n。即**f(n)=f(n-1)+f(n-2)**。

### 实现 ###

实现算法往往是简单的，及时是复杂算法也花费不了太多精力，所以将问题转换为数学问题是一种很好的选择。当前这种简单算法实现方式更为简单，而且往往不止一种方式。

### 递归 ###

public static int f(int n){
        if(n<=2) return n;
        int x = f(n-1)+f(n-2);
        return x;
    }

优点：可能是最好理解的算法了把。代码简单，好理解。  
缺点：计算次数颇多，有很多冗余计算。

## 迭代 ##

public static int f(int n){
        if(n<=2) return n;
        if first=1,second=2;
        int third=0;
        for(int i=3;i<=n;i++){
            third = first+second;
            first = second;
            second = third;
        }
        return third;
    }

优点: 基本没有冗余计算，效率高  
缺点: 谁能一次读完就理解的？

## 动态规划 ##

> 原文：动态规划是解决下面这些性质类问题的技术：  
> 1. 一个问题可以通过更小子问题的解决方法来解决（译者注：即问题的最优解 包含了其子问题的最优解，也就是最优子结构性质）。  
> 2. 有些子问题的解可能需要计算多次（译者注：也就是子问题重叠性质）。  
> 3. 子问题的解存储在一张表格里，这样每个子问题只用计算一次。  
> 4. 需要额外的空间以节省时间。

public static int[] A = new int[100];
    public static int f(int n){
        if(n<=2){
            A[n] = n;
        }
        if(A[n]>0){
            return A[n];
        } else {
            A[n] = f(n-1)+f(n-2);
            return A[n];
        }
    }

虽然没弄懂为啥叫动态规划，但是代码还是很清晰的。  
优点：已经计算过的结果就不需要再次计算了。空间换时间  
缺点：需要额外的开销。

### 问题： ###

例：公司招20名员工，每天招1个或者2个，问有多少种招法？