LeetCode LCR 104. 组合总和 Ⅳ

Categories:

题目描述
思路分析
1. 解法一：一维 DP（推荐）
相似题目

题目描述

✅ LCR 104. 组合总和 Ⅳ

思路分析

解法一：一维 DP（推荐）

核心思路：

dp[i] 表示凑出和为 i 的排列数量。

外层遍历目标和，内层遍历可选数字，保证顺序不同视作不同方案。

状态转移：dp[i] += dp[i - num]。

复杂度分析：

时间复杂度：O(target * n)，其中 n 表示数组长度。

空间复杂度：O(target)，用于 DP 数组。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }

        return (int) dp[target];
    }
}

func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1

	for i := 1; i <= target; i++ {
		for _, num := range nums {
			if i >= num {
				dp[i] += dp[i-num]
			}
		}
	}

	return dp[target]
}

相似题目

题目	难度	考察点
518. 零钱兑换 II	中等	动态规划
322. 零钱兑换	中等	动态规划
494. 目标和	中等	动态规划
279. 完全平方数	中等	动态规划
1155. 掷骰子等于目标和的方法数	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/27558928