C++ 递推实现：有 n 个木棍长度分别为 123……n现在明明有一把刀每次选定一个长度进行切割若木棍长度小于选定值则不切割多个木棍可以同时切割现在明明想计算至少需要切多少刀可以将所有木棍的长度都变为 0你能帮明明找找答案吗？1根木棍1：以长度1为单位切 1 刀后长度变为 0；总共至少需要 1 刀；2根木根12：以长度 1 为单位切 1 刀后长度变为 01再以长度 1 为单位切一刀后长度变为 00

#include using namespace std;

int main() { int n; cin >> n;

int dp[101] = {0};  // dp数组用于保存计算结果，dp[i]表示长度为i的木棍需要的最少刀数

for (int i = 1; i <= n; i++) {
    dp[i] = i;  // 初始化为最大值，即每根木棍都切一刀
    for (int j = 1; j <= i; j++) {
        dp[i] = min(dp[i], dp[i - j] + 1);  // 状态转移方程，取所有可能的切割长度的最小值
    }
}

cout << dp[n] << endl;  // 输出最终结果

return 0;

}