K Sum

又是一道O(n^3)级别的动态规划，实际上这道题的维度建立并不是很难想出来，状态转移方程也是相对来说很简单的，但是dp矩阵的初始化问题却比较麻烦，这里需要知道，首先在0个数可供选择且需要用0个数来达到0时的方法数为1，且用任意数中的0个数来达到0的方法数都是1，明确了这两个初始化条件，我们才好实现DP矩阵的递推，下面是状态方程，思路和背包问题一模一样

dp[i][j][q] = dp[i - 1][j][q] if j == 0 or q < A[i - 1] 这里是指的不能选择当前物品A[i - 1]的情况
dp[i][j][q] = dp[i - 1][j - 1][q - A[i - 1]] + dp[i - 1][j][q] 这里则是既可以选择拿也可以选择不拿的情况

高维的DP难点很多时候在于维度自己本身的一些限制条件以及高维dp矩阵初始化不好解决

class Solution:
    """
    @param A: An integer array.
    @param k: a positive integer (k <= length(A))
    @param target: integer
    @return an integer
    """
    def kSum(self, A, k, target):
        # write your code here
        n = len(A)
        dp = [[[0] * (target + 1) for _ in xrange(k + 1)] for _ in xrange(n + 1)]

        dp[0][0][0] = 1

        for i in xrange(1, n + 1):
            for j in xrange(k + 1):
                for q in xrange(target + 1):
                    dp[i][j][q] = dp[i - 1][j][q]
                    if q >= A[i - 1] and j > 0:
                        dp[i][j][q] += dp[i - 1][j - 1][q - A[i - 1]]

        return dp[n][k][target]