C++ 递推实现：切割木棍最小刀数 - 动态规划算法详解

一种实现思路是使用动态规划。创建一个长度为n+1的数组dp，dp[i]表示木棍长度为i时至少需要的刀数。\n\n首先初始化dp数组，将所有元素初始化为一个较大的值，表示目前还不知道需要多少刀。\n然后遍历长度为1到n的木棍，对于每个木棍长度i，遍历长度为1到i的切割长度j，如果切割长度j小于等于i，表示可以使用切割长度j将木棍长度i切割为0，需要的刀数为dp[i-j]+1，取这些刀数中的最小值更新dp[i]。\n最后，dp[n]即为所求的答案。\n\n以下是C++的实现代码：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <climits>\n\nint main() {\n int n;\n std::cin >> n;\n \n std::vector<int> dp(n+1, INT_MAX);\n dp[0] = 0; // 木棍长度为0时不需要刀\n \n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= i; j++) {\n dp[i] = std::min(dp[i], dp[i-j] + 1);\n }\n }\n \n std::cout << dp[n] << std::endl;\n \n return 0;\n}\n\n\n时间复杂度分析：外层循环遍历n次，内层循环遍历的次数为1到n的累加和，即1+2+...+n=(n+1)*n/2，因此总的时间复杂度为O(n^2)。