本文共 1542 字，大约阅读时间需要 5 分钟。

原题链接：https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。

总成本必须恰好等于 target 。

添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

解题思路

看数据范围，应该是和target有关的一个dp。细细想来就是完全背包。

设dp[i] 为成本刚好为i的能组成的最大的数。

代码

class Solution {
       public String largestNumber(int[] cost, int target) {
           String dp[] = new String[target + 1];        dp[0] = "0";        for(int i = 1; i <= target; i++)        {
               dp[i] = "";        }        String num[] = {
   "1", "2", "3", "4", "5", "6", "7", "8", "9"};        //先加大的数        for(int i = 8; i >= 0; i--)        {
               for(int j = cost[i]; j <= target; j++)            {
                   if(dp[j - cost[i]] != "" && mybigger(dp[j - cost[i]] + num[i], dp[j]))                {
                       dp[j] = dp[j - cost[i]] + num[i];                }            }        }        return dp[target] == "" ? "0" : dp[target].substring(1);    }    public boolean mybigger(String a, String b)    {
           if(a.length() != b.length())        {
               return a.length() > b.length();        }        int i = 0;        while(i < a.length())        {
               if(a.charAt(i) != b.charAt(i))            {
                   return a.charAt(i) > b.charAt(i);            }            i++;        }        return true;    }}

转载地址：http://jqhof.baihongyu.com/