-
状态及子问题
假设成本为target构成最大整数的最后一个数位是number,则剩下的最大整数为成本是target-cost[number],因此
状态:f(target) 为成本target的最大整数
子问题,f(target - cost[i]) 为成本target-cost[i]的最大整数
当然由于结果是字符串,应该还有一个判断两个数哪个大的函数 -
状态转移方程
f(i) = max( f(i - cost[k]) + k+1) k=1……9
这里错误,因为要正好用target成本,如何保证f( i - cost[k] )一定有数,或者说它不为空,如果是空的话,再加上k+1,不就说明前面的不符合条件硬加了一个数位。所以要判断他是不是空。 -
初始状态及边界条件
f(0) 一定是 “” -
计算顺序
从小到大
本题出现的错误有:①上面空的考虑 ② 应该比较的是 d[i] , dp[ i - cost[j] ] + j + 1,这次做题没有考虑。