LeetCode每日一题-2021-06-12-1449. 数位成本和为目标值的最大数字

LeetCode每日一题-2021-06-12-1449. 数位成本和为目标值的最大数字

  1. 状态及子问题
    假设成本为target构成最大整数的最后一个数位是number,则剩下的最大整数为成本是target-cost[number],因此
    状态:f(target) 为成本target的最大整数
    子问题,f(target - cost[i]) 为成本target-cost[i]的最大整数
    当然由于结果是字符串,应该还有一个判断两个数哪个大的函数

  2. 状态转移方程
    f(i) = max( f(i - cost[k]) + k+1) k=1……9
    这里错误,因为要正好用target成本,如何保证f( i - cost[k] )一定有数,或者说它不为空,如果是空的话,再加上k+1,不就说明前面的不符合条件硬加了一个数位。所以要判断他是不是空。

  3. 初始状态及边界条件
    f(0) 一定是 “”

  4. 计算顺序
    从小到大

本题出现的错误有:①上面空的考虑 ② 应该比较的是 d[i] , dp[ i - cost[j] ] + j + 1,这次做题没有考虑。

上一篇:[ SDOI2016 ] 数字配对


下一篇:postgresql关于in和exists使用