楼梯走法的动态规划算法

  有一座高度是10级台阶的楼梯，从下往上走，第步只能向上走1级或者2级，求一共有多少种走法？

---

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int *memo = NULL;
int steps = 10;

//普通递归求解
int stage(int n) {
    if (n == 1) {
        return 1;
    }

    if (n == 2) {
        return 2;
    }

    return stage(n-1) + stage(n-2);
}

//备忘录算法
int init_memo() {
    memo = (int*)malloc(sizeof(int));
    if (memo == NULL) {
        fprintf(stderr, "error on malloc\n");
        exit(EXIT_FAILURE);
    }

    for(int i=0; i<steps; i++) {
        memo[i] = -1;
    }

    return 0;
}

void free_memo() {
    if (memo != NULL) {
        free(memo);
    }
}

int memo_stage(int n) {
    int l,r;

    if (n == 1) {
        memo[n] = 1;
        return 1;
    }

    if (n == 2) {
        memo[n] = 2;
        return 2;
    }

    if (memo[n-1] > 0) {
        l = memo[n-1];
    } else {
        l = memo_stage(n-1);
       memo[n-1] = l;
    }

    if (memo[n-2] > 0) {
        r = memo[n-2];
    } else {
        r = memo_stage(n-2);
        memo[n-2] = r;
    }

    return l+r;
}

int main(int argc, char* argv[]) {
    printf("%d\n", stage(steps));

    init_memo();
    printf("%d\n", memo_stage(steps));
    free_memo();

    return 0;
}