|
| 1 | +// DP top-dowm approach |
| 2 | +classSolution { |
| 3 | +funcherryPickup(grid:Array<IntArray>):Int { |
| 4 | +val rows= grid.size |
| 5 | +val cols= grid[0].size |
| 6 | +var dp=Array (cols) {IntArray (cols) } |
| 7 | + |
| 8 | +for (rin (rows-1) downTo0) { |
| 9 | +val curDP=Array (cols) {IntArray (cols) } |
| 10 | +for (c1in0 until cols) { |
| 11 | +for (c2in c1+1 until cols) { |
| 12 | +var max=0 |
| 13 | +val curPick= grid[r][c1]+ grid[r][c2] |
| 14 | +for (c12in arrayOf(-1,0,1)) { |
| 15 | +for (c22in arrayOf(-1,0,1)) { |
| 16 | +val nC1= c1+ c12 |
| 17 | +val nC2= c2+ c22 |
| 18 | +if (nC1<0|| nC2== cols)continue |
| 19 | + max= maxOf( |
| 20 | + max, |
| 21 | + curPick+ dp[nC1][nC2] |
| 22 | + ) |
| 23 | + } |
| 24 | + } |
| 25 | + curDP[c1][c2]= max |
| 26 | + } |
| 27 | + } |
| 28 | + dp= curDP |
| 29 | + } |
| 30 | + |
| 31 | +return dp[0][cols-1] |
| 32 | + } |
| 33 | +} |
| 34 | + |
| 35 | +// Recursion + Memoization |
| 36 | +classSolution { |
| 37 | +funcherryPickup(grid:Array<IntArray>):Int { |
| 38 | +val rows= grid.size |
| 39 | +val cols= grid[0].size |
| 40 | +val dp=HashMap<String,Int>() |
| 41 | + |
| 42 | +fundfs(r:Int,c1:Int,c2:Int):Int { |
| 43 | +if (c1== c2|| minOf(c1, c2)<0|| maxOf(c1, c2)== cols)return0 |
| 44 | + dp["$r:$c1:$c2"]?.let {return it } |
| 45 | +if (r== rows-1)return grid[r][c1]+ grid[r][c2] |
| 46 | + |
| 47 | +var res=0 |
| 48 | +for (c12in arrayOf(-1,0,1)) { |
| 49 | +for (c22in arrayOf(-1,0,1)) { |
| 50 | + res= maxOf( |
| 51 | + res, |
| 52 | + dfs(r+1, c1+ c12, c2+ c22) |
| 53 | + ) |
| 54 | + } |
| 55 | + } |
| 56 | + |
| 57 | + res+= grid[r][c1]+ grid[r][c2] |
| 58 | + dp["$r:$c1:$c2"]= res |
| 59 | +return res |
| 60 | + } |
| 61 | + |
| 62 | +return dfs(0,0, cols-1) |
| 63 | + } |
| 64 | +} |