上下樓梯問題 & (籃球) 得分問題

簡介

先來描述一下問題，這裡以下樓梯為例：

有一個人下樓梯，一次可以走一階或兩階，假設總共有N階樓梯，共有幾總走法？例如 N = 3，他可以走 1 + 1 + 1 、1 + 2 或 2 + 1 三種走法。

實做一個程式能夠輸入 N，能回傳共有幾總走法。

演算法

這個問題直接使用 Bottom-Up 可能不容易思考，所以我們先利用遞迴的 Top-Down 思考邏輯來想這個問題，結果我們很容易就可以這樣想：

第N階的走法相當於在 N - 1 階的時候走一階過來，或者在 N - 2 階的時候走兩階過來；換句話說，就是第N階的走法等於N - 1階的走法加上N - 2階的走法。

所以我們就可以寫出遞迴式：

1
2
3

F(N) = F(N - 1) + F(N - 2)
F(1) = 1
F(2) = 2

列出來的式子和費波那西數列 (Fibonacci) 還蠻像的，我們可以用不同的方式去實做解這問題，這問題較適合用動態規劃 (Dynamic Programming) 去解，直接用 Divide and Conquer 會重覆計算子問題。由於此問題和費波那西數列相當相似，這邊只簡單實做迭代法和動態規劃的方式。

迭代法

由於每次新的問題的答案來自於前兩個問題，所以每次運算都保留前兩次的資料即可。如果新問題的答案來自前三個問題，則保留三個，以此類推。

動態規劃

使用遞迴的動態規劃則可以記錄過計算過的部分；另外也可以使用迴圈解的動態規劃，在思路上並不複雜，而且也減少Function call的消耗，這邊就不實做此方式，可參考費波那西數列這篇文章。

語法

C#

迭代法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DownStairs
{
    class Iterative
    {
        public static long DownStairs(int n)
        {
            long v1 = 1;
            long v2 = 2;
            long result = n;
            for (int i = 3; i <= n; ++i)
            {
                result = v2 + v1;
                v1 = v2;
                v2 = result;
            }
            return result;
        }
    }
}

動態規劃

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DownStairs
{
    class DynamicProgramming
    {
        static Dictionary<int, long> map = new Dictionary<int, long>() { { 1, 1 }, { 2, 2 } };
        public static long DownStairs(int n)
        {
            if (map.ContainsKey(n))
                return map[n];
            return map[n] = DownStairs(n - 1) + DownStairs(n - 2);
        }
    }
}

Java

迭代法

public class Iterative {
    public static long DownStairs(int n)
    {
        long v1 = 1;
        long v2 = 2;
        long result = n;
        for (int i = 2; i <= n; ++i)
        {
            result = v2 + v1;
            v1 = v2;
            v2 = result;
        }
        return result;
    }
}

動態規劃

import java.util.HashMap;
import java.util.Map;


public class DynamicProgramming {
    static Map map = new HashMap() {{ put(1, 1L); put(2, 2L); }};
    public static long DownStairs(int n)
    {
        if (map.containsKey(n))
            return map.get(n);
        map.put(n, DownStairs(n - 1) + DownStairs(n - 2));
        return map.get(n);
    }
}

C++

迭代法

Iterative.h

#ifndef ITERATIVE_H
#define ITERATIVE_H


class Iterative
{
    public:
        static long DownStairs(int n);
    protected:
    private:
};

#endif // ITERATIVE_H

Iterative.cpp

#include "Iterative.h"

long Iterative::DownStairs(int n)
{
    long v1 = 1;
    long v2 = 2;
    long result = n;
    for (int i = 3; i <= n; ++i)
    {
        result = v2 + v1;
        v1 = v2;
        v2 = result;
    }
    return result;
}

動態規劃

DynamicProgramming.h

#ifndef DYNAMICPROGRAMMING_H
#define DYNAMICPROGRAMMING_H

#include <map>

using namespace std;

class DynamicProgramming
{
    public:
        static long DownStairs(int n);
    protected:
    private:
        static pair init[];
        static map m;
};

#endif // DYNAMICPROGRAMMING_H

DynamicProgramming.cpp

#include "DynamicProgramming.h"

pair DynamicProgramming::init[] = { make_pair(1, 1), make_pair(2, 2) };
map DynamicProgramming::m(DynamicProgramming::init, DynamicProgramming::init + 2);
long DynamicProgramming::DownStairs(int n)
{
    if (DynamicProgramming::m.count(n) == 1)
        return DynamicProgramming::m[n];
    return DynamicProgramming::m[n] = DynamicProgramming::DownStairs(n - 1) + DynamicProgramming::DownStairs(n - 2);
}