Backpack 4

https://www.lintcode.com/problem/backpack-v/solution

这题我用的二维数组，memory limit exceeds，但应该是对的方法：

class Solution:
    """
    @param nums: an integer array and all positive numbers
    @param target: An integer
    @return: An integer
    """
    def backPackV(self, nums, target):
        # write your code here
        n = len(nums)
        dp= [[0]* (target+1) for _ in range(n+1)]
        for i in range(n+1):
            dp[i][0] = 1
        for i in range(1,n+1):
            for j in range(target+1):
                dp[i][j] = dp[i-1][j]
                if j >= nums[i-1]:
                    dp[i][j] += dp[i-1][j-nums[i-1]]
                #print("{} : {} -- {}".format(i,j,dp[i][j]))
        return dp[n][target]

试着优化一下成一位数组：