Java Prefix Sum Dynamic Programming
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int countOfPairs(int[] nums) {\n        \n        final int MOD = 1_000_000_007;\n        \n//         nums = new int[1000];\n//         Arrays.fill(nums, 1000);\n        \n        int n = nums.length;\n        long dp[][] = new long[n][1001];\n        \n        long preSum[][] = new long[n][1001];\n        \n        for(int i = 0; i <= nums[0]; i++) dp[0][i] = 1;\n        \n        for(int i = 0; i <= 1000; i++) {\n            if ( i-1 >= 0 ) {\n                preSum[0][i] = preSum[0][i-1] + dp[0][i];\n            } else{\n                preSum[0][i] = dp[0][i];\n            }\n             // System.out.print(preSum[0][i] + " ");\n        }\n         // System.out.println();\n        \n        \n        \n        for(int i = 1; i < n; i++) {\n            int num = nums[i];\n            for(int j = 0; j <= num; j++) {\n                int arr1 = j;\n                int arr2 = num-j;\n                \n                int beforenum = nums[i-1];\n                if ( beforenum >= num) {\n                    dp[i][arr1] = preSum[i-1][arr1];\n                } else{\n                    if ( arr1-(num-beforenum) >= 0 ) {\n                        dp[i][arr1] = preSum[i-1][arr1-(num-beforenum)];\n                        // System.out.println(arr1 + " " + arr2 + " " + before)\n                    }\n                }\n\n            }\n            \n            for(int j = 0; j <= 1000; j++) {\n                if ( j-1 >= 0 ) {\n                    preSum[i][j] = preSum[i][j-1] + dp[i][j];\n                } else{\n                    preSum[i][j] = dp[i][j];\n                }\n                preSum[i][j] %= MOD;\n            }\n        }\n        \n        long result = 0;\n        for(int i = 0; i < 1001; i++) {\n            result += dp[dp.length-1][i];\n            result  %= MOD;\n        }\n        \n        return (int)result;\n    }\n}\n```
['Dynamic Programming', 'Prefix Sum', 'Java']