UVa12955 - Factorial(動態規劃、背包問題)

題目大意

給你一個數字 n，想請問你最少可以用幾個 \(x!\) 來組合成 n。
其中 x 不一定都要相同數字，舉例： \(10 = 3! + 2! + 2!\)，因此我們使用 3 個 !，輸出 3。

題目連結

重點觀念

• 了解動態規劃

分析

• Coin Change Problem問題，但從找最大改成找最小
• 第一個迴圈設定為 9
  因為 \(9! = 362880\)，大於題目的最大 N
• 第二個迴圈設為 N，從 \(0~N\) 不斷進行無限背包

心得

難得輕鬆解，開心

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 100020
using namespace std;
int num[MAXN], n;
int f = 9;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL

    memset(num, 0x3f3f3f, sizeof(num)); //初始為無限大
    int sum = 1; //用於計算 factorial
    num[0] = 0; 
    for(int i = 1; i < 9; i++){
        sum *= i; //第 i factorial
        for(int j = sum; j < MAXN; j++){ //無限背包問題
            num[j] = min(num[j], num[j - sum]+1);
        }
    }

    //for(int i = 0; i < 30; i++) cout << num[i] << "\n";

    while(cin >> n){
        cout << num[n] << "\n";
    }
    return 0;
}