[Kotlin] Prefix Sum DP Solution
Approach\n Describe your approach to solving the problem. \n\nUse top-down dp to find max value of coin.\n\nSave every optimal value in dp table and use that va
# Approach\n<!-- Describe your approach to solving the problem. -->\n\nUse top-down dp to find max value of coin.\n\nSave every optimal value in dp table and use that value at next iteration.\n\nFlow goes like this:\n\n![Screenshot 1.png](https://assets.leetcode.com/users/images/abeeeae2-06c1-45ab-98ec-e99d61aaf750_1681554282.2017314.png)\n\n![Screenshot 2.png](https://assets.leetcode.com/users/images/4177b469-39d5-4caa-bde3-8a3e783423c1_1681554331.997646.png)\n\n![Screenshot 3.png](https://assets.leetcode.com/users/images/26f7b9be-ddfd-4433-9779-047d65f30417_1681554338.7622476.png)\n\n![Screenshot 4.png](https://assets.leetcode.com/users/images/f384cb7e-1371-4d88-8edf-c60e73325969_1681554343.7514818.png)\n\n![Screenshot 5.png](https://assets.leetcode.com/users/images/476ca714-3bfc-4901-b983-129cbe384803_1681554361.4551725.png)\n\n![Screenshot 6.png](https://assets.leetcode.com/users/images/a8dfd35d-1eff-4c1d-bb4d-cc743ec3cbef_1681554384.7290597.png)\n\n![Screenshot 7.png](https://assets.leetcode.com/users/images/781dd1af-b1c0-4fdf-bf95-481d894f4e1e_1681554394.5070295.png)\n\n![Screenshot 8.png](https://assets.leetcode.com/users/images/f0d1fc8a-21a2-4f23-baff-d3b77a3de1ef_1681554401.5723536.png)\n\n![Screenshot 9.png](https://assets.leetcode.com/users/images/5571a620-8666-4c19-98ed-9a06cdc9123e_1681554419.5653806.png)\n\n![Screenshot 10.png](https://assets.leetcode.com/users/images/59b913fc-712b-4493-8ff6-c96e3956570f_1681554441.5546458.png)\n\n![Screenshot 11.png](https://assets.leetcode.com/users/images/5ae3a06d-6a14-47c9-822d-49ddb10ccbe0_1681554486.8244655.png)\n\n\n# Complexity\n- Time complexity: $$O(n * k)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n * k)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n\n    fun maxValueOfCoins(piles: List<List<Int>>, k: Int): Int {\n       val dp = Array(piles.size + 1) { IntArray(k + 1) }\n\n        for (i in piles.lastIndex downTo 0) {\n            for (kIndex in k downTo 1) {\n                var currentValue = 0\n                var maxValue = dp[i + 1][kIndex]\n\n                for (j in 0 until minOf(kIndex, piles[i].size)) {\n                    currentValue += piles[i][j]\n                    maxValue = maxOf(maxValue, currentValue + dp[i + 1][kIndex - (j + 1)])\n                }\n\n                dp[i][kIndex] = maxValue\n            }\n        }\n\n        return dp[0][k]\n    }\n\n}\n```
['Array', 'Dynamic Programming', 'Prefix Sum', 'Kotlin']