Go (29ms beats 100% of golang submission) (memory:O(n)) DP with scroll arrays


  • 0
    O

    Sorry , My English is very poor!
    In my solution, I regard -n as (mid -n) and n as (mid + n) in my DP,which n >= 0 and mid is the sum of nums
    DP : dp[i+1][j +v] = dp[i][j] + dp[i+1][j +v] ,dp[i+1][j -v] = dp[i][j] + dp[i+1][j -v] (v =nums[i])
    I use two array to calculate this DP and I call it scroll arrays.It can reduce the memory we used effectively.
    In this solution I just use O(2 * 2 * mid),which mid is the sum of nums

    func findTargetSumWays(nums []int, S int) int {
        mid := 0
        for _,v := range nums{
            mid += v
        }
        dp := make([][]int, 2)
        for i,_:=range dp{
            dp[i] = make([]int, mid + mid + 1)
        }
        dp[0][mid] = 1
        for i,v := range nums{
            for j,_:= range dp[(i + 1)%2]{
                dp[(i + 1)%2][j] = 0
            }
            for j:=0; j <= mid + mid; j++{
                if j >= v {
                    dp[(i+1)%2][j-v] += dp[i%2][j]
                }
                if j + v <= mid + mid {
                   dp[(i+1)%2][j+v] += dp[i%2][j]
                }
            }
        }
        if S > mid || S < -mid{
            return 0
        }
       return dp[len(nums)%2][S+mid]
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.