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

• 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]
}
``````

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