力扣 剑指 Offer II 104. 排列的数目

题目来源：https://leetcode.cn/problems/D0F0SV/

大致题意：
给一个数组和整数 target，求出有多少个数组的子序列和为 target，顺序不同序列也视为不同的子序列

思路

设 dp[i] 表示子序列和为 i 的数目，若和为 i 的子序列最后一个元素为 nums[j]，那么有

• dp[i] = sum(dp[i - nums[j])，其中 i >= nums[j]

上述即为动态规划的状态转移方程

初始时，有 dp[0] = 1，即组成和为 0 的子序列只有 1 种

代码：

public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target + 1];
        // 初始化
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                int last = i - num;
                if (last >= 0) {
                    // 状态转移方程
                    dp[i] += dp[last];
                }
            }
        }
        return dp[target];
    }