题解 | 组合总数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数组空间消耗