[已解决]经典问题之爬楼梯（c）

#include <iostream>
#include <map>

using std::map;
int foo(int n, int k, map <int, int> MAP) {
        int count = 0;
        if (not(n)) return 1;
        if (MAP.count(n)) return MAP[n];
        else if (n >= k) {
                for (int i = 1; i <= k; ++i) count += foo(n - i, k, MAP);
        }
        else count += foo(n, n, MAP);
        MAP[n] = count;
        return count;
}

using std::cout, std::endl;
int main(void) {
        map <int, int> MAP;
        int n = 10, k = 4;
        cout << foo(n, k, MAP) << endl;
        return 0;
}

import java.util.*;

public class Main
{
        public static int foo(int n, int k, Map <Integer, Integer> map) {
            int count = 0;
            if (n == 0) return 1;
            if (map.containsKey(n)) return map.get(n);
            else if (n >= k) {
                for (int i = 1; i <= k; ++i) count += foo(n - i, k, map);
            }
            else count += foo(n, n, map);
            map.put(n, count);
            return count;
        }
        
        public static void main(String[] args) {
            Map <Integer, Integer> map = new HashMap <Integer, Integer>();
            int n = 10, k = 4;
                System.out.println(foo(n, k, map));
        }
}

def foo(n, k, MAP = dict()):
    count = 0
    if not n: return 1
    if n in MAP.keys(): return MAP[n]
    elif n >= k:
        for i in range(1, k + 1):
            count += foo(n - i, k, MAP)
    else: count += foo(n, n, MAP)
    MAP[n] = count
    return count

n, k = 10, 4
print(foo(n, k))