89. K数之和
中文English
给定 n 个不同的正整数,整数 k(k <= n)以及一个目标数字 target。
在这 n 个数里面找出 k 个数,使得这 k 个数的和等于目标数字,求问有多少种方案?
样例
样例1
输入:
List = [1,2,3,4]
k = 2
target = 5
输出: 2
说明: 1 + 4 = 2 + 3 = 5
样例2
输入:
List = [1,2,3,4,5]
k = 3
target = 6
输出: 1
说明: 只有这一种方案。 1 + 2 + 3 = 6
输入测试数据 (每行一个参数)如何理解测试数据?
动态规划 + 三维数组
class Solution: """ @param A: An integer array @param k: A positive integer (k <= length(A)) @param target: An integer @return: An integer """ def kSum(self, A, k, target): # write your code here #大致思路,动态规划,当前f[i][j][t]的次数为j-1次数下t - A[i - 1]的次数 + j次数下t的次数 #边界情况,当target为0的时候,方案数为1,当如果当前A[i - 1]小于t(当前目标),则说明可以加上 #j - 1次数下 t - A[i - 1]的方案种数 #初始化 length = len(A) dp = [[[0 for _ in range(target + 1)] for _ in range(k + 1)] for _ in range(length + 1)] #如果target为0的话,只有一种可能,并且是k为0的情况才存在1种方案数 for i in range(length + 1): dp[i][0][0] = 1 #其他情况方案数为0 #计算顺序 #最外层循环,循环A for i in range(1, length + 1): for j in range(1, k + 1): #z作为暂定目标值 for z in range(1, target + 1): pre = 0 #如果当前目标值z - A[i - 1] >= 0,说明是可以加上之前[i - 1][j - 1][z - A[i - 1]]的方案种数的 if (z - A[i - 1] >= 0): pre = dp[i - 1][j - 1][z - A[i - 1]] #最终存在两种可能,一种是加上之前z - A[i - 1]的方案种数,一种是之前dp[i - 1][j][z]的方案种数 dp[i][j][z] = pre + dp[i - 1][j][z] #最终返回target return dp[length][k][target]
滚动数组优化版本:
class Solution: """ @param A: An integer array @param k: A positive integer (k <= length(A)) @param target: An integer @return: An integer """ def kSum(self, A, k, target): # write your code here #大致思路,动态规划,存在两种情况,一种是如果当前暂定目标值 > 当前A[i - 1]值的话,就可以加上 #j - 1的方案种数,否则的话只能加上之前[j][t]1的方案种数 #滚动数组优化 #初始化 length = len(A) dp = [[[0 for _ in range(target + 1)] for _ in range(k + 1)] for _ in range(2)] #如果k为0,target为0 for i in range(length + 1): dp[i%2][0][0] = 1 #其他情况方案种数为0 #计算顺序 for i in range(1, length + 1): for j in range(1, k + 1): for z in range(1, target + 1): pre = 0 #如果当前暂定目标值 - A[i - 1] >= 0,说明是可以加上之前j - 1下z - A[i - 1]1的方案种数 if (z - A[i - 1] >= 0): pre = dp[(i - 1)%2][j - 1][z - A[i - 1]] #最后必须要加上j个下z目标值的方案种数 dp[i%2][j][z] = pre + dp[(i - 1)%2][j][z] return dp[length%2][k][target]