Участник:UlitinAleksander/form-largest-integer-with-digits-that-add-up-to-target

Материал из DISCOPAL
Перейти к: навигация, поиск

Java

https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/

class Solution {
 
    String[] dp ;
 
    public String largestNumber(int[] cost, int target) {
 
		dp = new String[target+1]; 
 
        find(cost, target);
 
        return dp[target] == ""?"0":dp[target]; 
    }
 
    public String find(int[] cost, int target){
 
        if (target == 0) return ""; 
        if (dp[target]!=null) return dp[target]; 
 
        String curr = "0"; 
        for(int i = 8; i >= 0; i--){ 
 
            if (target - cost[i] >= 0){ 
                String x = find(cost, target - cost[i]); 
                if (x.equals("0")) continue; 
                x = String.valueOf((i+1))+x;
 
                if(curr.equals("0") || x.length() > curr.length()) curr = x; 
 
            }
        }
 
        dp[target] = curr;
        return dp[target];
    }
}