|
| 1 | +// dp |
| 2 | +classSolution { |
| 3 | +funnumberOfArithmeticSlices(nums:IntArray):Int { |
| 4 | +var res=0 |
| 5 | +val dp=HashMap<Pair<Int,Long>,Int>() |
| 6 | + |
| 7 | +for (iin0 until nums.size) { |
| 8 | +for (jin0 until i) { |
| 9 | +val d= nums[i].toLong()- nums[j] |
| 10 | + dp[i to d]= (dp[i to d]?:0)+1+ (dp[j to d]?:0) |
| 11 | + res+= (dp[j to d]?:0) |
| 12 | + } |
| 13 | + } |
| 14 | + |
| 15 | +return res |
| 16 | + } |
| 17 | +} |
| 18 | + |
| 19 | +// recursion + memoization |
| 20 | +classSolution { |
| 21 | +funnumberOfArithmeticSlices(nums:IntArray):Int { |
| 22 | +val dp=HashMap<String,Int>() |
| 23 | +val count=HashMap<Long,MutableList<Int>>() |
| 24 | + |
| 25 | + nums.forEachIndexed { i, n-> |
| 26 | + count.getOrPut(n.toLong()) {mutableListOf() }.apply { add(i) } |
| 27 | + } |
| 28 | + |
| 29 | +fundfs(i:Int,d:Long,s:Int):Int { |
| 30 | + dp["$i:$d:$s"]?.let {return it } |
| 31 | + |
| 32 | +var res=if (s>2)1else0 |
| 33 | + count[nums[i]+ d]?.forEach { j-> |
| 34 | +if (j> i) res+= dfs(j, d, s+1) |
| 35 | + } |
| 36 | + |
| 37 | + dp["$i:$d:$s"]= res |
| 38 | +return res |
| 39 | + } |
| 40 | + |
| 41 | +var res=0 |
| 42 | +for (iin0 until nums.size) { |
| 43 | +for (jin i+1 until nums.size) |
| 44 | + res+= dfs(j, nums[j].toLong()- nums[i],2) |
| 45 | + } |
| 46 | + |
| 47 | +return res |
| 48 | + } |
| 49 | +} |