C++ 算法：切割木棍的最小刀数

C++ 实现：切割木棍的最小刀数

有 n 个木棍，长度分别为 1, 2, 3……n，现在明明有一把刀，每次选定一个长度进行切割，若木棍长度小于选定值则不切割，多个木棍可以同时切割，现在明明想计算至少需要切多少刀可以将所有木棍的长度都变为 0，你能帮明明找找答案吗？

例如：

1 根木棍（1）：以长度 1 为单位，切 1 刀后长度变为 0；总共至少需要 1 刀；
2 根木根（1, 2）：以长度 1 为单位，切 1 刀后长度变为 0, 1，再以长度 1 为单位，切一刀后长度变为 0, 0；总共至少需要 2 刀；
3 根木棍（1, 2, 3）：以长度 1 为单位，切一刀后长度变为 0, 1, 2，再以长度 1 为单位，切一刀后长度变为 0, 0, 1，再以长度 1 为单位，切一刀后长度变为 0, 0, 0，此种切法总共需要 3 刀。若先以长度 2 为单位，切一刀后长度变为 1, 0, 1，再以长度 1 为单位，切一刀后长度变为 0, 0, 0，此种切法总共需要 2 刀。所以总共至少需要 2 刀；

输入描述

输入一个整数 n，为木棍的个数。（其中 1≤n≤100）

输出描述

输出当所有木棍长度都变为 0 时至少需要的刀数

样例 1

输入
6
输出
3

样例 2

输入
20
输出
5

解法一：动态规划

思路：

定义一个数组 dp，dp[i] 表示当有 i 根木棍时，至少需要的刀数；
初始化 dp 数组为无穷大，dp[0] = 0；
遍历每个木棍长度 j，从 1 到 n，更新 dp 数组：
- 对于每个 dp[j]，遍历长度为 k 的刀，从 1 到 j，更新 dp[j] = min(dp[j], dp[j-k]+1)；
返回 dp[n]。

代码实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> dp(n+1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int k = 1; k <= j; k++) {
                dp[j] = min(dp[j], dp[j-k]+1);
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

解法二：数学方法

思路：

观察题目中给出的样例，可以发现当 n 为奇数时，至少需要切割 n/2+1 次；当 n 为偶数时，至少需要切割 n/2 次；
因此，可以直接根据 n 的奇偶性得到最终的刀数。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n % 2 == 0) {
        cout << n/2 << endl;
    } else {
        cout << n/2 + 1 << endl;
    }
    return 0;
}