Form Largest Integer With Digits That Add up to Target

// Accepted solution for LeetCode #1449: Form Largest Integer With Digits That Add up to Target
class Solution {
    public String largestNumber(int[] cost, int target) {
        final int inf = 1 << 30;
        int[][] f = new int[10][target + 1];
        int[][] g = new int[10][target + 1];
        for (var e : f) {
            Arrays.fill(e, -inf);
        }
        f[0][0] = 0;
        for (int i = 1; i <= 9; ++i) {
            int c = cost[i - 1];
            for (int j = 0; j <= target; ++j) {
                if (j < c || f[i][j - c] + 1 < f[i - 1][j]) {
                    f[i][j] = f[i - 1][j];
                    g[i][j] = j;
                } else {
                    f[i][j] = f[i][j - c] + 1;
                    g[i][j] = j - c;
                }
            }
        }
        if (f[9][target] < 0) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 9, j = target; i > 0;) {
            if (j == g[i][j]) {
                --i;
            } else {
                sb.append(i);
                j = g[i][j];
            }
        }
        return sb.toString();
    }
}

// Accepted solution for LeetCode #1449: Form Largest Integer With Digits That Add up to Target
func largestNumber(cost []int, target int) string {
	const inf = 1 << 30
	f := make([][]int, 10)
	g := make([][]int, 10)
	for i := range f {
		f[i] = make([]int, target+1)
		g[i] = make([]int, target+1)
		for j := range f[i] {
			f[i][j] = -inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= 9; i++ {
		c := cost[i-1]
		for j := 0; j <= target; j++ {
			if j < c || f[i][j-c]+1 < f[i-1][j] {
				f[i][j] = f[i-1][j]
				g[i][j] = j
			} else {
				f[i][j] = f[i][j-c] + 1
				g[i][j] = j - c
			}
		}
	}
	if f[9][target] < 0 {
		return "0"
	}
	ans := []byte{}
	for i, j := 9, target; i > 0; {
		if g[i][j] == j {
			i--
		} else {
			ans = append(ans, '0'+byte(i))
			j = g[i][j]
		}
	}
	return string(ans)
}

# Accepted solution for LeetCode #1449: Form Largest Integer With Digits That Add up to Target
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        f = [[-inf] * (target + 1) for _ in range(10)]
        f[0][0] = 0
        g = [[0] * (target + 1) for _ in range(10)]
        for i, c in enumerate(cost, 1):
            for j in range(target + 1):
                if j < c or f[i][j - c] + 1 < f[i - 1][j]:
                    f[i][j] = f[i - 1][j]
                    g[i][j] = j
                else:
                    f[i][j] = f[i][j - c] + 1
                    g[i][j] = j - c
        if f[9][target] < 0:
            return "0"
        ans = []
        i, j = 9, target
        while i:
            if j == g[i][j]:
                i -= 1
            else:
                ans.append(str(i))
                j = g[i][j]
        return "".join(ans)

// Accepted solution for LeetCode #1449: Form Largest Integer With Digits That Add up to Target
/**
 * [1449] Form Largest Integer With Digits That Add up to Target
 *
 * Given an array of integers cost and an integer target, return the maximum integer you can paint under the following rules:
 *
 * 	The cost of painting a digit (i + 1) is given by cost[i] (0-indexed).
 * 	The total cost used must be equal to target.
 * 	The integer does not have 0 digits.
 *
 * Since the answer may be very large, return it as a string. If there is no way to paint any integer given the condition, return "0".
 *  
 * Example 1:
 *
 * Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
 * Output: "7772"
 * Explanation: The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "977", but "7772" is the largest number.
 * Digit    cost
 *   1  ->   4
 *   2  ->   3
 *   3  ->   2
 *   4  ->   5
 *   5  ->   6
 *   6  ->   7
 *   7  ->   2
 *   8  ->   5
 *   9  ->   5
 *
 * Example 2:
 *
 * Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
 * Output: "85"
 * Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.
 *
 * Example 3:
 *
 * Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
 * Output: "0"
 * Explanation: It is impossible to paint any integer with total cost equal to target.
 *
 *  
 * Constraints:
 *
 * 	cost.length == 9
 * 	1 <= cost[i], target <= 5000
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/
// discuss: https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn largest_number(cost: Vec<i32>, target: i32) -> String {
        let mut dp = vec![0; target as usize + 1];

        for i in 1..=target {
            dp[i as usize] = -1;
            for j in 0..9 {
                if i >= cost[j] && dp[(i - cost[j]) as usize] >= 0 {
                    dp[i as usize] = std::cmp::max(dp[i as usize], dp[(i - cost[j]) as usize] + 1);
                }
            }
        }

        if dp[target as usize] < 0 {
            return "0".to_string();
        }

        let mut result = String::new();
        let mut i = target;
        for j in (0..9).rev() {
            while i >= cost[j] && dp[(i - cost[j]) as usize] == dp[i as usize] - 1 {
                result.push(((j + 1) as u8 + b'0') as char);
                i -= cost[j];
            }
        }

        result
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_1449_example_1() {
        let cost = vec![4, 3, 2, 5, 6, 7, 2, 5, 5];
        let target = 9;

        let result = "7772".to_string();

        assert_eq!(Solution::largest_number(cost, target), result);
    }

    #[test]
    fn test_1449_example_2() {
        let cost = vec![7, 6, 5, 5, 5, 6, 8, 7, 8];
        let target = 12;

        let result = "85".to_string();

        assert_eq!(Solution::largest_number(cost, target), result);
    }

    #[test]
    fn test_1449_example_3() {
        let cost = vec![2, 4, 6, 2, 4, 6, 4, 4, 4];
        let target = 5;

        let result = "0".to_string();

        assert_eq!(Solution::largest_number(cost, target), result);
    }
}

// Accepted solution for LeetCode #1449: Form Largest Integer With Digits That Add up to Target
function largestNumber(cost: number[], target: number): string {
    const inf = 1 << 30;
    const f: number[][] = Array(10)
        .fill(0)
        .map(() => Array(target + 1).fill(-inf));
    const g: number[][] = Array(10)
        .fill(0)
        .map(() => Array(target + 1).fill(0));
    f[0][0] = 0;
    for (let i = 1; i <= 9; ++i) {
        const c = cost[i - 1];
        for (let j = 0; j <= target; ++j) {
            if (j < c || f[i][j - c] + 1 < f[i - 1][j]) {
                f[i][j] = f[i - 1][j];
                g[i][j] = j;
            } else {
                f[i][j] = f[i][j - c] + 1;
                g[i][j] = j - c;
            }
        }
    }
    if (f[9][target] < 0) {
        return '0';
    }
    const ans: number[] = [];
    for (let i = 9, j = target; i; ) {
        if (g[i][j] === j) {
            --i;
        } else {
            ans.push(i);
            j = g[i][j];
        }
    }
    return ans.join('');
}