[LC] 2218 Maximum Value of K Coins From Piles

Java

import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/">Maximum Value of K Coins From Piles</a>
 * 数组；动态规划；前缀和
 */
class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int[] f = new int[k + 1];
        Arrays.fill(f, -1);
        f[0] = 0;
        for (List<Integer> pile : piles) {
            for (int i = k; i > 0; --i) {
                int value = 0;
                for (int t = 1; t <= pile.size(); ++t) {
                    value += pile.get(t - 1);
                    if (i >= t && f[i - t] != -1) {
                        f[i] = Math.max(f[i], f[i - t] + value);
                    }
                }
            }
        }
        return f[k];
    }
}

Go

func maxValueOfCoins(piles [][]int, k int) int {
    f := make([]int, k+1)
    for i := range f {
        f[i] = -1
    }
    f[0] = 0
    for _, pile := range piles {
        for i := k; i > 0; i-- {
            value := 0
            for t := 1; t <= len(pile); t++ {
                value += pile[t-1]
                if i >= t && f[i-t] != -1 {
                    f[i] = max(f[i], f[i-t]+value)
                }
            }
        }
    }
    return f[k]
}

JavaScript

/**
 * @param {number[][]} piles
 * @param {number} k
 * @return {number}
 */
var maxValueOfCoins = function (piles, k) {
    let f = new Array(k + 1).fill(-1);
    f[0] = 0;
    for (let pile of piles) {
        for (let i = k; i > 0; --i) {
            let value = 0;
            for (let t = 1; t <= pile.length; t++) {
                value += pile[t - 1];
                if (i >= t && f[i - t] !== -1) {
                    f[i] = Math.max(f[i], f[i - t] + value);
                }
            }
        }
    }
    return f[k];
};

PHP

class Solution {

    /**
     * @param Integer[][] $piles
     * @param Integer $k
     * @return Integer
     */
    function maxValueOfCoins(array $piles, int $k): int {
        $f = array_fill(0, $k + 1, -1);
        $f[0] = 0;
        foreach ($piles as $pile) {
            for ($i = $k; $i > 0; --$i) {
                $value = 0;
                for ($t = 1; $t <= count($pile); ++$t) {
                    $value += $pile[$t - 1];
                    if ($i >= $t && $f[$i - $t] != -1) {
                        $f[$i] = max($f[$i], $f[$i - $t] + $value);
                    }
                }
            }
        }
        return $f[$k];
    }
}