剑指 Offer II 104. 排列的数目
算法记录
LeetCode 题目:
给定一个由 不同 正整数组成的数组 nums ,和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。
说明
一、题目
数组中的数字可以在一次排列中出现任意次,但是顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。
二、分析
- 和找硬币的题很相似,只是可以存在相同数量但顺序不同的额结果。
- 也就是分发的结果不再是前一种结果
+1
,而是加上前面的所有结果集,因为可以完成1 : N
的配对。 - 零肯定能组成零的,那就是初始条件有
dp[0] = 0
。
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 1; i <= target; i++) {
for(int num : nums) {
if(num <= i) dp[i] += dp[i - num];
}
}
return dp[target];
}
}
总结
熟悉状态状态转移方程的定义。
版权声明:本文为MTYSYS19990212原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。