用動態規劃解決問題：基本觀念(有重疊子問題的問題)

動態規劃(Dynamic Programming，簡稱DP)是一種解決問題的技巧，主要被用來優化那些「記不住自己過去曾解出來的答案所以只好重複再解」的演算法，讓它們可以「記憶」已經找出來的答案，從而不斷利用，以大大降低時間複雜度(從指數級降到線性)。

記憶法(Memoization)與製表法(Tabulation)

以費氏數列來說明。費氏數列又稱費布那西(Fibonacci)數列，它是一種發散數列，第1項的值為0，第2項的值為1，第#{{n}}#項(#{{ n \geq 3 }}#)的值為第#{{n - 1}}#項和第#{{n - 2}}#項的總和。費氏數列看起來會長得像以下這樣：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

以數學函數#{{F(n)}}#來表示費氏數列的第#{{n}}#項數值，可以寫成：

#{{{
\begin{eqnarray}
F(1) &=& 0 \nonumber \\
F(2) &=& 1 \nonumber \\
F(n) &=& F(n - 1) + F(n - 2), \text{where } n \geq 3 \nonumber \\
\end{eqnarray}
}}}#

不過由於寫程式習慣從0開始數，所以最好還是將費氏數列的第一項設計為#{{F(0)}}#，也就是：

#{{{
\begin{eqnarray}
F(0) &=& 0 \nonumber \\
F(1) &=& 1 \nonumber \\
F(n) &=& F(n - 1) + F(n - 2), \text{where } n \geq 2 \nonumber \\
\end{eqnarray}
}}}#

這篇文章之後都會用#{{F(0)}}#作為費氏數列的第一項。

根據定義，當我們要計算#{{F(5)}}#時，要先去算#{{F(4)}}#和#{{F(3)}}#，而要算#{{F(4)}}#時，就要先算#{{F(3)}}#和#{{F(2)}}#。有沒有發現#{{F(3)}}#此時會被算兩次？當然，#{{F(2)}}#也是類似的情形，同樣會被計算多次。如果我們畫出#{{F(5)}}#的遞迴樹(Recursion Tree)，會長成以下這樣：

                          F(5)
                          /  \
                         /    \
                        /      \
                       /        \
                      /          \
                     /            \
                    /              \
                   /                \
                  /                  \
                 /                    \
                /                      \
              F(4)                     F(3)
              /  \                     /  \
             /    \                   /    \
            /      \                 /      \
           /        \               /        \
          /          \             /          \
       F(3)         F(2)         F(2)         F(1)
       /  \         /  \         /  \
      /    \       /    \       /    \
   F(2)    F(1) F(1)   F(0)  F(1)    F(0)
   /  \
  /    \
F(1)  F(0)

可以明顯發現有重複的子樹存在，因此如果直接利用費氏數列的定義寫成如下的程式，運算起來效能是很差的。時間複雜度為#{{O(2^n)}}#。

pub fn fibonacci(n: usize) -> usize {
    match n {
        0 => 0,
        1 => 1,
        n => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

public static int fibonacci(final int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

function fibonacci(n: number): number {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

func Fibonacci(n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		return Fibonacci(n-1) + Fibonacci(n-2)
	}
}

我們可以利用動態規劃來優化以上的遞迴函數(Recursive Function)。動態規劃的作法，大方向分為兩種，第一種是記憶法，第二種製表法，前者用於優化從上而下(Top Down)的演算法，後者用於產生由下而上(Bottom Up)的演算法。

Top-down：記憶法(Memoization)

Top-down就是從目的開始，往下完成所需的細節。例如要蓋一棟3層樓的房子，為了要蓋第3層，就必須要先蓋第2層。為了要蓋第2層，就必須要先蓋第1層。

遞迴函數通常就是屬於Top-down的問題解決方法，這種解法通常很容易就能被(抽象、粗略地)理解，但具體要動作的時候就很難知道要從哪裡開始、該怎麼進行，因為它會把一個大問題自動分成許多小問題。然而，這些小問題可能會像上面提到的費氏數列函數那樣「會重複」，如果演算法沒有機制去避免重複解這些同樣的問題，那這個演算法就可以使用動態規劃的記憶法來優化，大大減少遞迴函數的呼叫次數。

以上面提到的費氏數列函數來說，我們可以建立一個大小為n + 1的dp陣列，將陣列元素值初始化為能夠判斷是否已經儲存結果的值(以費氏數列來說可以設成0或是整數的最大值)。第一次計算#{{F(k)}}#，#{{k <= n}}#，在計算出#{{F(k - 1) + F(k - 2)}}#的結果後，把結果儲存到dp[k]中，之後如果又要計算#{{F(k)}}#，只需要從dp[k]中取得已知的結果就好了。

所以把費氏數列的遞迴函數加入動態規劃的記憶法後，程式碼如下：

fn fibonacci_inner(dp: &mut [usize], n: usize) -> usize {
    match n {
        0 => 0,
        1 => 1,
        n => {
            if dp[n] == 0 {
                dp[n] = fibonacci_inner(dp, n - 1) + fibonacci_inner(dp, n - 2);
            }

            dp[n]
        }
    }
}

pub fn fibonacci(n: usize) -> usize {
    let mut dp = vec![0; n + 1];

    fibonacci_inner(&mut dp, n)
}

static int fibonacciInner(final int[] dp, final int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            if (dp[n] == 0) {
                dp[n] = fibonacciInner(dp, n - 1) + fibonacciInner(dp, n - 2);
            }

            return dp[n];
    }
}

public static int fibonacci(final int n) {
    final int[] dp = new int[n + 1];
    
    return fibonacciInner(dp, n);
}

function fibonacciInner(dp: number[], n: number) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            if (dp[n] === 0) {
                dp[n] = fibonacciInner(dp, n - 1) + fibonacciInner(dp, n - 2);
            }

            return dp[n];
    }
}

function fibonacci(n: number): number {
    const dp = new Array(n + 1).fill(0);

    return fibonacciInner(dp, n);
}

func fibonacciInner(dp []int, n int) int {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	default:
		if dp[n] == 0 {
			dp[n] = fibonacciInner(dp, n-1) + fibonacciInner(dp, n-2)
		}

		return dp[n]
	}
}

func Fibonacci(n int) int {
	dp := make([]int, n+1)

	return fibonacciInner(dp, n)
}

此時#{{F(5)}}#的遞迴樹就會變成：

                          F(5)
                          /  \
                         /    \
                        /      \
                       /        \
                      /          \
                     /            \
                    /              \
                   /                \
                  /                  \
                 /                    \
                /                      \
              F(4)                     F(3)
              /  \
             /    \
            /      \
           /        \
          /          \
       F(3)         F(2)
       /  \
      /    \
   F(2)    F(1)
   /  \
  /    \
F(1)  F(0)

時間複雜度頓時減少為#{{O(n)}}#了。

Bottom-up：製表法(Tabulation)

Bottom-up就是先完成細節，再逐步達成目的。例如要蓋一棟3層樓的房子，蓋好第1層後蓋第2層，蓋好第2層後蓋第3層。

Bottom-up的問題解決方法，通常不容易被理解，但具體要動作的時候可以清楚地知道要從哪裡開始、該怎麼進行。

對於一個可以用動態規劃記憶法優化的演算法，我們其實也可以直接用製表法來改寫它。如果原本是遞迴的演算法，也可以順便把遞迴轉成迭代。首先要做的就是觀察Top-down的問題解決順序，建立出足夠儲存過程中所有問題的解的儲存空間，然後從最小的問題開始解，把解儲存起來，以便之後解大問題的時候取用。

以上面提到的費氏數列函數來說，我們可以建立一個大小為n + 1的dp陣列，dp[i]預計要來用來儲存#{{F(i)}}#的解。先根據費氏數列的基本案例(base case)，把dp[0]指派為0、dp[1]指派為1，接著利用迴圈計算#{{i = 2 \text{ to } n}}#時，dp[i]的結果。最後算出來的dp[n]，就是F(n)的值。

所以把費氏數列的遞迴函數用動態規劃的製表法改寫後，程式碼如下：

pub fn fibonacci(n: usize) -> usize {
    let mut dp = Vec::with_capacity(n + 1);

    unsafe {
        answers.set_len(n + 1);
    }

    dp[0] = 0;
    dp[1] = 1;

    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    dp[n]
}

public static int fibonacci(final int n) {
    final int[] dp = new int[n + 1];

    dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

function fibonacci(n: number) {
    const dp = new Array<number>(n + 1);

    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2;i <= n;i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

func Fibonacci(n int) int {
	dp := make([]int, n+1)

	dp[1] = 1

	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}

	return dp[n]
}

以上的迭代版的費氏數列函數，時間複雜度為#{{O(n)}}#。

當然，以上程式還有能夠小改進的地方，因為在算#{{F(i)}}#的時候只有#{{F(i - 1)}}#和#{{F(i - 2)}}#的解會被使用到，所以我們只需儲存前兩個問題的解就好了。將程式碼優化如下：

pub fn fibonacci(n: usize) -> usize {
    match n {
        0 => 0,
        _ => {
            let mut before_previous_answer = 0;
            let mut previous_answer = 1;
            let mut answer = 1;

            for _ in 2..=n {
                answer = previous_answer + before_previous_answer;

                before_previous_answer = previous_answer;
                previous_answer = answer;
            }

            answer
        }
    }
}

public static int fibonacci(final int n) {
    if (n == 0) {
        return 0;
    } else {
        int beforePreviousAnswer = 0;
        int previousAnswer = 0;
        int answer = 0;

        for (int i = 2; i <= n; ++i) {
            answer = previousAnswer + beforePreviousAnswer;

            beforePreviousAnswer = previousAnswer;
            previousAnswer = answer;
        }

        return answer;
    }
}

function fibonacci(n: number) {
    if (n === 0) {
        return 0;
    } else {
        let beforePreviousAnswer = 0;
        let previousAnswer = 0;
        let answer = 0;

        for (let i = 2;i <= n;i++) {
            answer = previousAnswer + beforePreviousAnswer;

            beforePreviousAnswer = previousAnswer;
            previousAnswer = answer;
        }

        return answer;
    }
}

func Fibonacci(n int) int {
	if n == 0 {
		return 0
	} else {
		beforePreviousAnswer := 0
		previousAnswer := 0
		answer := 0

		for i := 2; i <= n; i++ {
			answer = previousAnswer + beforePreviousAnswer

			beforePreviousAnswer = previousAnswer
			previousAnswer = answer
		}

		return answer
	}
}

製表法必須從最小的問題開始，一步步地將問題擴大到我們的想要解決的大問題，在這個過程中很可能會去解到不需要解的小問題。因此在理想的情況下(忽略為了分割子問題而產生的開支)或是某些情況下(製表法需要去解非常多不需要解的小問題)，用Top-down搭配記憶法來解決問題會是比較好的方式。

有重疊子問題的問題

當一個問題能被分解成子問題，而子問題再繼續分解下去的子問題有重複的情況時，表示這個問題有重疊子問題(Overlapping Subproblem)。動態規劃可以使這些重疊子問題只會被計算一次。

底下會再舉幾個有重疊子問題的題型。

爬樓梯問題(排列)

一個有著#{{n}}#階的階梯，如果每步可以爬1階、2階或3階，要爬完#{{n}}#階，有幾種走法？

先以Top-down的方式來思考這個問題。因為在最後一步要爬完#{{n}}#階，所以在執行最後一步前，有可能已經爬完了#{{n - 1}}#階、#{{n - 2}}#階和#{{n - 3}}#階，那麼從底部爬到第#{{n}}#階的走法之數量就會是爬完#{{n - 1}}#、#{{n - 2}}#和#{{n - 3}}#階的走法之數量的總和。最小的問題為爬0階(1種走法，那就是不走)、爬1階(1種走法)和爬2階(2種走法，一步2階或是兩步1階)。

以程式來解題的話，我們可以寫出以下的遞迴函數：

pub fn climb_stairs(n: usize) -> usize {
    match n {
        0 | 1 => 1,
        2 => 2,
        _ => {
            climb_stairs(n - 1) + climb_stairs(n - 2) + climb_stairs(n - 3)
        }
    }
}

public static int climbStairs(final int n) {
    switch (n) {
        case 0:
        case 1:
            return 1;
        case 2:
            return 2;
        default:
            return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3);
    }
}

function climbStairs(n: number): number {
    switch (n) {
        case 0:
        case 1:
            return 1;
        case 2:
            return 2;
        default:
            return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3);
    }
}

func ClimbStairs(n int) int {
	switch n {
	case 0, 1:
		return 1
	case 2:
		return 2
	default:
		return ClimbStairs(n-1) + ClimbStairs(n-2) + ClimbStairs(n-3)
	}
}

當然，這個函數的效能很差，時間複雜度為#{{O(3^n)}}#，先不管它。因為還有個更嚴重的地方，那就是這個程式目前只能固定地計算每步爬1階、2階或3階，功能實在太弱了！所以我們要把程式改成可以從函數參數輸入一步允許走幾階(假設每次至少會走一步，每步至少會走1階，且會遞增輸入)。而因為輸入的最小步可能會大於1階，所以需要注意到無解的情形(例如一步可以走3階或7階，那麼要爬到第11階就是不可能的)。若是無解，則把結果當作0。

程式強化功能後如下：

pub fn climb_stairs(single_step: &[usize], n: usize) -> usize {
    if n < single_step[0] {
        if n == 0 {
            1
        } else {
            0
        }
    } else {
        let mut sum = 0;

        for k in single_step.iter().copied() {
            if n < k {
                break;
            }

            sum += climb_stairs(single_step, n - k);
        }

        sum
    }
}

public static int climbStairs(final int[] singleStep, final int n) {
    if (n < singleStep[0]) {
        return n == 0 ? 1 : 0;
    } else {
        int sum = 0;

        for (final int k : singleStep) {
            if (n < k) {
                break;
            }

            sum += climbStairs(singleStep, n - k);
        }

        return sum;
    }
}

function climbStairs(singleStep: number[], n: number) {
    if (n < singleStep[0]) {
        return n === 0 ? 1 : 0;
    } else {
        let sum = 0;

        for (const k of singleStep) {
            if (n < k) {
                break;
            }

            sum += climbStairs(singleStep, n - k);
        }

        return sum;
    }
}

func ClimbStairs(singleStep []int, n int) int {
	if n < singleStep[0] {
		if n == 0 {
			return 1
		} else {
			return 0
		}
	} else {
		sum := 0

		for _, k := range singleStep {
			if n < k {
				break
			}

			sum += ClimbStairs(singleStep, n-k)
		}

		return sum
	}
}

由於以上程式碼有重疊子問題，所以可以用動態規劃的記憶法來優化或是用製表法將其改寫成迭代函數。

以製表法為例，改寫如下：

pub fn climb_stairs(single_step: &[usize], n: usize) -> usize {
    let mut dp = vec![0; n + 1];

    dp[0] = 1;

    for i in 1..=n {
        if i >= single_step[0] {
            let mut sum = 0;

            for k in single_step.iter().copied() {
                if i < k {
                    break;
                }

                sum += dp[i - k];
            }

            dp[i] = sum;
        }
    }

    dp[n]
}

public static int climbStairs(final int[] singleStep, final int n) {
    final int[] dp = new int[n + 1];

    dp[0] = 1;

    for (int i = 1; i <= n; ++i) {
        if (i >= singleStep[0]) {
            int sum = 0;

            for (final int k : singleStep) {
                if (i < k) {
                    break;
                }

                sum += dp[i - k];
            }

            dp[i] = sum;
        }
    }

    return dp[n];
}

function climbStairs(singleStep: number[], n: number) {
    const dp = new Array<number>(n + 1).fill(0);

    dp[0] = 1;

    for (let i = 1;i <= n;i++) {
        if (i >= singleStep[0]) {
            let sum = 0;

            for (const k of singleStep) {
                if (i < k) {
                    break;
                }

                sum += dp[i - k];
            }

            dp[i] = sum;
        }
    }

    return dp[n];
}

func ClimbStairs(singleStep []int, n int) int {
	dp := make([]int, n+1)

	dp[0] = 1

	for i := 1; i <= n; i++ {
		if i >= singleStep[0] {
			sum := 0

			for _, k := range singleStep {
				if i < k {
					break
				}

				sum += dp[i-k]
			}

			dp[i] = sum
		}
	}

	return dp[n]
}

還可以繼續優化：

pub fn climb_stairs(single_step: &[usize], n: usize) -> usize {
    let mut dp = vec![0; n + 1];

    dp[0] = 1;

    for i in single_step[0]..=n {
        let mut sum = 0;

        for k in single_step.iter().copied() {
            if i < k {
                break;
            }

            sum += dp[i - k];
        }

        dp[i] = sum;
    }

    dp[n]
}

public static int climbStairs(final int[] singleStep, final int n) {
    final int[] dp = new int[n + 1];

    dp[0] = 1;

    for (int i = singleStep[0]; i <= n; ++i) {
        int sum = 0;

        for (final int k : singleStep) {
            if (i < k) {
                break;
            }

            sum += dp[i - k];
        }

        dp[i] = sum;
    }

    return dp[n];
}

function climbStairs(singleStep: number[], n: number) {
    const dp = new Array<number>(n + 1).fill(0);

    dp[0] = 1;

    for (let i = singleStep[0];i <= n;i++) {
        let sum = 0;

        for (const k of singleStep) {
            if (i < k) {
                break;
            }

            sum += dp[i - k];
        }

        dp[i] = sum;
    }

    return dp[n];
}

func ClimbStairs(singleStep []int, n int) int {
	dp := make([]int, n+1)

	dp[0] = 1

	for i := singleStep[0]; i <= n; i++ {
		sum := 0

		for _, k := range singleStep {
			if i < k {
				break
			}

			sum += dp[i-k]
		}

		dp[i] = sum
	}

	return dp[n]
}

貼磁磚問題(排列)

現在有一個尺寸為#{{X \times Y}}#的平面，要用尺寸為#{{X \times 1}}#的磁磚貼滿(不留縫隙)，磁磚只能被橫貼(#{{X \times 1}}#)和直貼(#{{1 \times X}}#)，有幾種方式？

先以Top-down的方式來思考這個問題。首先要知道#{{X}}#和#{{Y}}#誰大誰小，若#{{X > Y}}#，則只有一種貼法(全部橫貼)；若#{{X = Y}}#，則只有兩種貼法(全部橫貼或是全部直貼)。若#{{ X < Y }}#，且最後一步是橫貼的話，表示在執行最後一步前，已經貼滿了#{{X \times (Y - 1)}}#，而如果最後一步是直貼的話，表示先前已經貼滿了#{{X \times (Y - X)}}#，並且又再直貼了#{{X - 1}}#個磁磚，所以還剩最後一個磁磚要直貼。也就是說，全部貼滿有幾種方式就是，貼滿#{{X \times (Y - 1)}}#有幾種方式和貼滿#{{X \times (Y - X)}}#有幾種方式的總和。

以程式來解題的話，我們可以寫出以下的遞迴函數：

pub fn place_tiles(x: usize, y: usize) -> usize {
    match x.cmp(&y) {
        Ordering::Greater => 1,
        Ordering::Equal => 2,
        Ordering::Less => {
            place_tiles(x, y - 1) + place_tiles(x, y - x)
        }
    }
}

public static int placeTiles(final int x, final int y) {
    if (x > y) {
        return 1;
    } else if (x == y) {
        return 2;
    } else {
        return placeTiles(x, y - 1) + placeTiles(x, y - x);
    }
}

function placeTiles(x: number, y: number): number {
    if (x > y) {
        return 1;
    } else if (x === y) {
        return 2;
    } else {
        return placeTiles(x, y - 1) + placeTiles(x, y - x);
    }
}

func PlaceTiles(x int, y int) int {
	if x > y {
		return 1
	} else if x == y {
		return 2
	} else {
		return PlaceTiles(x, y-1) + PlaceTiles(x, y-x)
	}
}

由於以上程式碼有重疊子問題，所以可以用動態規劃的記憶法來優化或是用製表法將其改寫成迭代函數。

以製表法為例，改寫如下：

pub fn place_tiles(x: usize, y: usize) -> usize {
    if x > y {
        1
    } else if x == y {
        2
    } else {
        let mut dp = Vec::with_capacity(y + 1);

        unsafe {
            dp.set_len(y + 1);
        }

        for i in 1..=y {
            match x.cmp(&i) {
                Ordering::Greater => {
                    dp[i] = 1;
                }
                Ordering::Equal => {
                    dp[i] = 2;
                }
                Ordering::Less => {
                    dp[i] = dp[i - 1] + dp[i - x];
                }
            }
        }

        dp[y]
    }
}

public static int placeTiles(final int x, final int y) {
    if (x > y) {
        return 1;
    } else if (x == y) {
        return 2;
    } else {
        final int[] dp = new int[y + 1];

        for (int i = 1; i <= y; ++i) {
            if (x > i) {
                dp[i] = 1;
            } else if (x == i) {
                dp[i] = 2;
            } else {
                dp[i] = dp[i - 1] + dp[i - x];
            }
        }

        return dp[y];
    }
}

function placeTiles(x: number, y: number) {
    if (x > y) {
        return 1;
    } else if (x === y) {
        return 2;
    } else {
        const dp = new Array<number>(y + 1);

        for (let i = 1;i <= y;i++) {
            if (x > i) {
                dp[i] = 1;
            } else if (x === i) {
                dp[i] = 2;
            } else {
                dp[i] = dp[i - 1] + dp[i - x];
            }
        }

        return dp[y];
    }
}

func PlaceTiles(x int, y int) int {
	if x > y {
		return 1
	} else if x == y {
		return 2
	} else {
		dp := make([]int, y+1)

		for i := 1; i <= y; i++ {
			if x > i {
				dp[i] = 1
			} else if x == i {
				dp[i] = 2
			} else {
				dp[i] = dp[i-1] + dp[i-x]
			}
		}
		return dp[y]
	}
}

因為原本函數的x參數並不會在遞迴時發生變化，所以在使用動態規劃時，只需建立出一維陣列就好了。

買東西問題(組合)

一片薯餅10元、一杯可樂20元、一個漢堡40元，剛好買到#{{n}}#元有幾種組合？

先以Top-down的方式來思考這個問題。首先要注意的是，這是一個「組合」(Combination)問題，例如「先買兩個漢堡，再買一杯可樂」(40→80→100)和「先買一杯可樂，再買兩個漢堡」(20→60→100)只能算是同一種買法。

如果我們永遠按照物品的某種順序來購買的話，就可以得到該組合唯一的一種排列方式。

那麼假設我們從便宜的物品開始買。因為在最後一步要買到#{{n}}#元，所以在執行最後一步前，有可能已經買到了#{{n - 10}}#元、#{{n - 20}}#元或#{{n - 40}}#元，所以從0元買到#{{n}}#元的組合方式之數量為買到#{{n - 10}}#元、#{{n - 20}}#元和#{{n - 40}}#元的組合方式之數量的總和。若倒數第二步是買到#{{n - 10}}#元(最後一步花了10元)，那麼倒數第三步就只能是買到#{{n - 10 - 10}}#元(倒數第二步只能花10元)；若倒數第二步是買到#{{n - 20}}#元(最後一步花了20元)，那麼倒數第三步就可以是買到#{{n - 10 - 10}}#元或是#{{n - 10 - 20}}#元(倒數第二步花了20元或是10元)……依此類推。最小的問題為買到0元(1種買法，那就是都不買)、買到1~9元(0種買法，無法達成)、買到10元(1種買法，買1個薯餅)和買到11 ~ 39元，但是買到11 ~ 39元我們不太能夠直接知道有多少種買法，所以不要把它當作是基本案例(base case)。

以程式來解題的話，我們可以寫出以下的遞迴函數：

fn buy_items_inner(target_cost: usize, max_cost: usize) -> usize {
    match target_cost {
        0 | 10 => 1,
        _ => {
            if target_cost <= 39 {
                if target_cost >= 20 {
                    match max_cost {
                        20 | 40 => buy_items_inner(target_cost - 10, 10) + buy_items_inner(target_cost - 20, 20),
                        _ => buy_items_inner(target_cost - 10, 10)
                    }
                } else if target_cost >= 10 {
                    buy_items_inner(target_cost - 10, 10)
                } else {
                    0
                }
            } else {
                match max_cost {
                    40 => buy_items_inner(target_cost - 10, 10) + buy_items_inner(target_cost - 20, 20) + buy_items_inner(target_cost - 40, 40),
                    20 => buy_items_inner(target_cost - 10, 10) + buy_items_inner(target_cost - 20, 20),
                    _ => buy_items_inner(target_cost - 10, 10)
                }
            }
        }
    }
}

pub fn buy_items(target_cost: usize) -> usize {
    buy_items_inner(target_cost, 40)
}

static int buyItemsInner(final int targetCost, final int maxCost) {
    switch (targetCost) {
        case 0:
        case 10:
            return 1;
        default:
            if (targetCost <= 39) {
                if (targetCost >= 20) {
                    switch (maxCost) {
                        case 40:
                        case 20:
                            return buyItemsInner(targetCost - 10, 10) + buyItemsInner(targetCost - 20, 20);
                        default:
                            return buyItemsInner(targetCost - 10, 10);
                    }
                } else if (targetCost >= 10) {
                    return buyItemsInner(targetCost - 10, 10);
                } else {
                    return 0;
                }
            } else {
                switch (maxCost) {
                    case 40:
                        return buyItemsInner(targetCost - 10, 10) + buyItemsInner(targetCost - 20, 20) + buyItemsInner(targetCost - 40, 40);
                    case 20:
                        return buyItemsInner(targetCost - 10, 10) + buyItemsInner(targetCost - 20, 20);
                    default:
                        return buyItemsInner(targetCost - 10, 10);
                }
            }
    }
}

public static int buyItems(final int targetCost) {
    return buyItemsInner(targetCost, 40);
}

function buyItemsInner(targetCost: number, maxCost: number): number {
    switch (targetCost) {
        case 0:
        case 10:
            return 1;
        default:
            if (targetCost <= 39) {
                if (targetCost >= 20) {
                    switch (maxCost) {
                        case 40:
                        case 20:
                            return buyItemsInner(targetCost - 10, 10) + buyItemsInner(targetCost - 20, 20);
                        default:
                            return buyItemsInner(targetCost - 10, 10);
                    }
                } else if (targetCost >= 10) {
                    return buyItemsInner(targetCost - 10, 10);
                } else {
                    return 0;
                }
            } else {
                switch (maxCost) {
                    case 40:
                        return buyItemsInner(targetCost - 10, 10) + buyItemsInner(targetCost - 20, 20) + buyItemsInner(targetCost - 40, 40);
                    case 20:
                        return buyItemsInner(targetCost - 10, 10) + buyItemsInner(targetCost - 20, 20);
                    default:
                        return buyItemsInner(targetCost - 10, 10);
                }
            }
    }
}

function buyItems(targetCost: number) {
    return buyItemsInner(targetCost, 40);
}

func buyItemsInner(targetCost int, maxCost int) int {
	switch targetCost {
	case 0, 10:
		return 1
	default:
		if targetCost <= 39 {
			if targetCost >= 20 {
				switch maxCost {
				case 20, 40:
					return buyItemsInner(targetCost-10, 10) + buyItemsInner(targetCost-20, 20)
				default:
					return buyItemsInner(targetCost-10, 10)
				}
			} else if targetCost >= 10 {
				return buyItemsInner(targetCost-10, 10)
			} else {
				return 0
			}
		} else {
			switch maxCost {
			case 40:
				return buyItemsInner(targetCost-10, 10) + buyItemsInner(targetCost-20, 20) + buyItemsInner(targetCost-40, 40)
			case 20:
				return buyItemsInner(targetCost-10, 10) + buyItemsInner(targetCost-20, 20)
			default:
				return buyItemsInner(targetCost-10, 10)
			}
		}
	}
}

func BuyItemsInner(targetCost int) int {
	return buyItemsInner(targetCost, 40)
}

當然，這個函數的效能很差，先不管它。因為還有個更嚴重的地方，那就是這個程式目前只能固定地用單價10、20、40元的商品來計算，功能實在太弱了！所以我們要把程式改成可以從函數參數輸入商品的單價(假設至少有一種商品，每種商品的單價至少會有1元，且會遞增輸入)。

程式強化功能後如下：

fn buy_items_inner(items_cost: &[usize], target_cost: usize, max_cost_index: usize) -> usize {
    if target_cost < items_cost[0] {
        if target_cost == 0 {
            1
        } else {
            0
        }
    } else {
        let mut sum = 0;

        for (cost_index, cost) in items_cost.iter().copied().enumerate() {
            if target_cost < cost || cost_index > max_cost_index {
                break;
            }

            sum += buy_items_inner(items_cost, target_cost - cost, cost_index);
        }

        sum
    }
}

pub fn buy_items(items_cost: &[usize], target_cost: usize) -> usize {
    buy_items_inner(items_cost, target_cost, items_cost.len() - 1)
}

static int buyItemsInner(final int[] itemsCost, final int targetCost, final int maxCostIndex) {
    if (targetCost < itemsCost[0]) {
        return targetCost == 0 ? 1 : 0;
    } else {
        int sum = 0;

        for (int costIndex = 0; costIndex < itemsCost.length; ++costIndex) {
            final int cost = itemsCost[costIndex];

            if (targetCost < cost || costIndex > maxCostIndex) {
                break;
            }

            sum += buyItemsInner(itemsCost, targetCost - cost, costIndex);
        }

        return sum;
    }
}

public static int buyItems(final int[] itemsCost, final int targetCost) {
    return buyItemsInner(itemsCost, targetCost, itemsCost.length - 1);
}

function buyItemsInner(itemsCost: number[], targetCost: number, maxCostIndex: number) {
    if (targetCost < itemsCost[0]) {
        return targetCost === 0 ? 1 : 0;
    } else {
        let sum = 0;

        for (let costIndex = 0;costIndex < itemsCost.length;costIndex++) {
            const cost = itemsCost[costIndex];

            if (targetCost < cost || costIndex > maxCostIndex) {
                break;
            }

            sum += buyItemsInner(itemsCost, targetCost - cost, costIndex);
        }

        return sum;
    }
}

function buyItems(itemsCost: number[], targetCost: number) {
    return buyItemsInner(itemsCost, targetCost, itemsCost.length - 1);
}

func buyItemsInner(itemsCost []int, targetCost int, maxCostIndex int) int {
	if targetCost < itemsCost[0] {
		if targetCost == 0 {
			return 1
		} else {
			return 0
		}
	} else {
		sum := 0

		for costIndex, cost := range itemsCost {
			if targetCost < cost || costIndex > maxCostIndex {
				break
			}

			sum += buyItemsInner(itemsCost, targetCost-cost, costIndex)
		}

		return sum
	}
}

func BuyItems(itemsCost []int, targetCost int) int {
	return buyItemsInner(itemsCost, targetCost, len(itemsCost)-1)
}

由於以上程式碼有重疊子問題，所以可以用動態規劃的記憶法來優化或是用製表法將其改寫成迭代函數。

以製表法為例，改寫如下：

pub fn buy_items(items_cost: &[usize], target_cost: usize) -> usize {
    let items_cost_len = items_cost.len();

    let mut dp = vec![vec![0; items_cost_len]; target_cost + 1];

    for i in 0..items_cost_len {
        dp[0][i] = 1;
    }

    for max_cost_index in 0..items_cost_len {
        for i in items_cost[0]..=target_cost {
            let mut sum = 0;

            for (cost_index, cost) in items_cost.iter().copied().enumerate() {
                if i < cost || cost_index > max_cost_index {
                    break;
                }

                sum += dp[i - cost][cost_index];
            }

            dp[i][max_cost_index] = sum;
        }
    }

    dp[target_cost][items_cost_len - 1]
}

public static int buyItems(final int[] itemsCost, final int targetCost) {
    final int itemsCostLen = itemsCost.length;

    final int[][] dp = new int[targetCost + 1][itemsCostLen];


    for (int i = 0; i < itemsCostLen; ++i) {
        dp[0][i] = 1;
    }

    for (int maxCostIndex = 0; maxCostIndex < itemsCostLen; ++maxCostIndex) {
        for (int i = itemsCost[0]; i <= targetCost; ++i) {
            int sum = 0;

            for (int costIndex = 0; costIndex < itemsCostLen; ++costIndex) {
                final int cost = itemsCost[costIndex];

                if (i < cost || costIndex > maxCostIndex) {
                    break;
                }

                sum += dp[i - cost][costIndex];
            }

            dp[i][maxCostIndex] = sum;
        }
    }

    return dp[targetCost][itemsCostLen - 1];
}

function buyItems(itemsCost: number[], targetCost: number) {
    const itemsCostLen = itemsCost.length;

    const dp = new Array<number[]>(targetCost + 1);

    dp[0] = new Array<number>(itemsCostLen).fill(1);

    for (let i = 1;i <= targetCost;i++) {
        dp[i] = new Array<number>(itemsCostLen).fill(0);
    }

    for (let maxCostIndex = 0;maxCostIndex < itemsCostLen;maxCostIndex++) {
        for (let i = itemsCost[0];i <= targetCost;i++) {
            let sum = 0;

            for (let costIndex = 0;costIndex < itemsCost.length;costIndex++) {
                const cost = itemsCost[costIndex];

                if (i < cost || costIndex > maxCostIndex) {
                    break;
                }

                sum += dp[i - cost][costIndex];
            }

            dp[i][maxCostIndex] = sum;
        }
    }

    return dp[targetCost][itemsCostLen - 1];
}

func BuyItems(itemsCost []int, targetCost int) int {
	itemsCostLen := len(itemsCost)

	dp := make([][]int, targetCost+1)

	for i := 0; i <= targetCost; i++ {
		dp[i] = make([]int, itemsCostLen)
	}

	for i := 0; i < itemsCostLen; i++ {
		dp[0][i] = 1
	}

	for maxCostIndex := 0; maxCostIndex < itemsCostLen; maxCostIndex++ {
		for i := itemsCost[0]; i <= targetCost; i++ {
			sum := 0

			for costIndex, cost := range itemsCost {
				if i < cost || costIndex > maxCostIndex {
					break
				}

				sum += dp[i-cost][costIndex]
			}

			dp[i][maxCostIndex] = sum
		}
	}

	return dp[targetCost][itemsCostLen-1]
}

觀察以上程式，可以發現dp陣列能簡化成長度為amount + 1的一維陣列。程式繼續優化如下：

pub fn buy_items(items_cost: &[usize], target_cost: usize) -> usize {
    let mut dp = vec![0; target_cost + 1];

    dp[0] = 1;

    for cost in items_cost.iter().copied() {
        for i in cost..=target_cost {
            dp[i] += dp[i - cost];
        }
    }

    dp[target_cost]
}

public static int buyItems(final int[] itemsCost, final int targetCost) {
    final int[] dp = new int[targetCost + 1];

    dp[0] = 1;

    for (int cost : itemsCost) {
        for (int i = cost; i <= targetCost; ++i) {
            dp[i] += dp[i - cost];
        }
    }

    return dp[targetCost];
}

function buyItems(itemsCost: number[], targetCost: number) {
    const dp = new Array<number>(targetCost + 1).fill(0);

    dp[0] = 1;

    for (const cost of itemsCost) {
        for (let i = cost;i <= targetCost;i++) {
            dp[i] += dp[i - cost];
        }
    }

    return dp[targetCost];
}

func BuyItems(itemsCost []int, targetCost int) int {
	dp := make([]int, targetCost+1)

	dp[0] = 1

	for _, cost := range itemsCost {
		for i := cost; i <= targetCost; i++ {
			dp[i] += dp[i-cost]
		}
	}

	return dp[targetCost]
}

而以上程式，又可以再優化成：

pub fn buy_items(items_cost: &[usize], target_cost: usize) -> usize {
    let mut dp = vec![0; target_cost + 1];

    dp[0] = 1;

    for i in (items_cost[0]..=target_cost).step_by(items_cost[0]) {
        dp[i] = 1;
    }

    for cost in items_cost[1..].iter().copied() {
        for i in cost..=target_cost {
            dp[i] += dp[i - cost];
        }
    }

    dp[target_cost]
}

public static int buyItems(final int[] itemsCost, final int targetCost) {
    final int[] dp = new int[targetCost + 1];

    dp[0] = 1;

    for (int i = itemsCost[0]; i <= targetCost; i += itemsCost[0]) {
        dp[i] = 1;
    }

    for (int costIndex = 1; costIndex < itemsCost.length; ++costIndex) {
        final int cost = itemsCost[costIndex];

        for (int i = cost; i <= targetCost; ++i) {
            dp[i] += dp[i - cost];
        }
    }

    return dp[targetCost];
}

function buyItems(itemsCost: number[], targetCost: number) {
    const dp = new Array<number>(targetCost + 1).fill(0);

    dp[0] = 1;

    for (let i = itemsCost[0];i <= targetCost;i += itemsCost[0]) {
        dp[i] = 1;
    }

    itemsCost = itemsCost.slice(1);

    for (const cost of itemsCost) {
        for (let i = cost;i <= targetCost;i++) {
            dp[i] += dp[i - cost];
        }
    }

    return dp[targetCost];
}

func BuyItems(itemsCost []int, targetCost int) int {
	dp := make([]int, targetCost+1)

	dp[0] = 1

	for i := itemsCost[0]; i <= targetCost; i += itemsCost[0] {
		dp[i] = 1
	}

	for _, cost := range itemsCost[1:] {
		for i := cost; i <= targetCost; i++ {
			dp[i] += dp[i-cost]
		}
	}

	return dp[targetCost]
}

經過簡化並優化之後的函數，彷彿使用了一個全新的演算法。以自然語言來描述的話，就是：先找出只能買第一個商品時的所有組合，再利用這個結果，找出第二個商品也能買時的所有組合，再利用這個結果，找出第三個商品也能買時的所有組合……

以題目來說明，重溫一下題目：一片薯餅10元、一杯可樂20元、一個漢堡40元，剛好買到#{{n}}#元有幾種組合？

若#{{n = 40}}#，當只能買第一個商品時，0元、10元、20元、30元、40元各會有一種組合，也就是買0片、1片、2片、3片、4片薯餅。

當第二個商品也能買時，組合就會是0片薯餅+0杯可樂(0元)、0片薯餅+1杯可樂(20元)、0片薯餅+2杯可樂(40元)、1片薯餅+0杯可樂(10元)、1片薯餅+1杯可樂(30元)、2片薯餅+0杯可樂(20元)、2片薯餅+1杯可樂(40元)、3片薯餅+0杯可樂(30元)、4片薯餅+0杯可樂(40元)。排序一下：

0元：0片薯餅+0杯可樂
10元：1片薯餅+0杯可樂
20元：2片薯餅+0杯可樂、0片薯餅+1杯可樂
30元：3片薯餅+0杯可樂、1片薯餅+1杯可樂
40元：4片薯餅+0杯可樂、2片薯餅+1杯可樂、0片薯餅+2杯可樂

當第三個商品也能買時：

0元：0片薯餅+0杯可樂
10元：1片薯餅+0杯可樂
20元：2片薯餅+0杯可樂、0片薯餅+1杯可樂
30元：3片薯餅+0杯可樂、1片薯餅+1杯可樂
40元：4片薯餅+0杯可樂、2片薯餅+1杯可樂、0片薯餅+2杯可樂、0片薯餅+1個漢堡

觀察一下上述兩清單的規律，就可以知道為什麼程式要這樣算了。

可以再利用「最大公因數(GCD)」來修改這個程式，避免價格太大時，每次迭代i只加1造成的浪費(太多0種組合)。有關於最大公因數的找法可以查看這篇文章：

https://magiclen.org/prime-factorization-gcd-lcm

程式修改如下：

pub fn buy_items(items_cost: &[usize], target_cost: usize) -> usize {
    let mut dp = vec![0; target_cost + 1];

    dp[0] = 1;

    for i in (items_cost[0]..=target_cost).step_by(items_cost[0]) {
        dp[i] = 1;
    }

    let mut step = items_cost[0];

    for cost in items_cost[1..].iter().copied() {
        step = gcd(step, cost);

        for i in (cost..=target_cost).step_by(step) {
            dp[i] += dp[i - cost];
        }
    }

    dp[target_cost]
}

pub fn gcd(mut a: usize, mut b: usize) -> usize {
    if b > a {
        swap(&mut a, &mut b);
    }

    let mut m = a % b;

    while m != 0 {
        a = b;
        b = m;
        m = a % b;
    }

    b
}

public static int buyItems(final int[] itemsCost, final int targetCost) {
    final int[] dp = new int[targetCost + 1];

    dp[0] = 1;

    for (int i = itemsCost[0]; i <= targetCost; i += itemsCost[0]) {
        dp[i] = 1;
    }

    int step = itemsCost[0];

    for (int costIndex = 1; costIndex < itemsCost.length; ++costIndex) {
        final int cost = itemsCost[costIndex];

        step = gcd(step, cost);

        for (int i = cost; i <= targetCost; i += step) {
            dp[i] += dp[i - cost];
        }
    }

    return dp[targetCost];
}

public static int gcd(int a, int b) {
    if (b > a) {
        final int c = b;
        b = a;
        a = c;
    }

    int m = a % b;

    while (m != 0) {
        a = b;
        b = m;
        m = a % b;
    }

    return b;
}

function buyItems(itemsCost: number[], targetCost: number) {
    const dp = new Array<number>(targetCost + 1).fill(0);

    dp[0] = 1;

    for (let i = itemsCost[0];i <= targetCost;i += itemsCost[0]) {
        dp[i] = 1;
    }

    let step = itemsCost[0];

    itemsCost = itemsCost.slice(1);

    for (const cost of itemsCost) {
        step = gcd(step, cost);

        for (let i = cost;i <= targetCost;i += step) {
            dp[i] += dp[i - cost];
        }
    }

    return dp[targetCost];
}

function gcd(a: number, b: number) {
    if (b > a) {
        const c = b;
        b = a;
        a = c;
    }

    let m = a % b;

    while (m !== 0) {
        a = b;
        b = m;
        m = a % b;
    }

    return b;
}

func BuyItems(itemsCost []int, targetCost int) int {
	dp := make([]int, targetCost+1)

	dp[0] = 1

	for i := itemsCost[0]; i <= targetCost; i += itemsCost[0] {
		dp[i] = 1
	}

	step := itemsCost[0]

	for _, cost := range itemsCost[1:] {
		step = Gcd(step, cost)

		for i := cost; i <= targetCost; i += step {
			dp[i] += dp[i-cost]
		}
	}

	return dp[targetCost]
}

func Gcd(a int, b int) int {
	if b > a {
		c := b
		b = a
		a = c
	}

	m := a % b

	for m != 0 {
		a = b
		b = m
		m = a % b
	}

	return b
}