题解 | 组合总数IV
题干分析
题设给予我们一个可使用的正整数数组（数组内元素不重复）要求我们任意使用数组中的数组进排列，使得排列后所得的总和为给出的目标整数。求符合条件的排列总数。
算法思路
本题本质上是一个比较灵活的爬楼梯问题，我们可以将目标整数视作我们需要爬的楼梯总数，所给的正整数数组即为我们一步能够跨过的台阶数，计算排列的总数就理所应当的变为求爬上目标台阶数的方法数。
因此有DP状态转移方程：
以及初始条件：
实现代码
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned> dp(target + 1, 0); // unsigned 防溢出
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (auto n : nums) {
if (n <= i) dp[i] += dp[i - n];
}
}
return static_cast<int>(dp[target]);
}
};
复杂度分析
- 时间复杂度：从1到target各迭代一次，时间复杂度
- 空间复杂度：dp数组空间消耗
查看1道真题和解析