问题四(填空题)
【问题描述】
小蓝有一个整数，初始值为 1 ，他可以花费一些代价对这个整数进行变换。
小蓝可以花费 1 的代价将整数增加 1 。
小蓝可以花费 3 的代价将整数增加一个值，这个值是整数的数位中最大的那个（1 到 9）。
小蓝可以花费 10 的代价将整数变为原来的 2 倍。
例如，如果整数为 16，花费 3 将整数变为 22 。
又如，如果整数为 22，花费 1 将整数变为 23 。
又如，如果整数为 23，花费 10 将整数变为 46 。
请问，如果要将整数从初始值 1 变为 2024，请问最少需要多少代价？
【答案提交】 79
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
状态转移方程 dp[i+1]=Math.min(dp[i+1],dp[i]+1);
dp[i+dg(i)]=Math.min(dp[i+dg(i)],dp[i]+3)
dp[2*i]=Math.min(dp[2*i],dp[i]+10)
public class Test { public static void main(String[] args) {int dp[]=new int[2025];Arrays.fill(dp,Integer.MAX_VALUE);//设dp[x] 为1到达x的最大代价。dp[1]=0;//表示到达1的代价为0//循环模拟三种条件，更新最小代价for (int i = 1; i <=2024; i++) {if(i+1<=2024){//条件1dp[i+1]=Math.min(dp[i+1],dp[i]+1);}if(i+d(i)<=2024){//条件2dp[i+d(i)]=Math.min(dp[i+d(i)],dp[i]+3);}if(i*2<=2024){//条件3dp[i*2]=Math.min(dp[i*2],dp[i]+10);}}System.out.println(dp[2024]);//输出1-2024最小代价}/*** 求个位数* @param i* @return*/private static int d(int i){return i%10;}}