整数变换的代价

1.题目：

小蓝有一个整数，初始值为 1 ，他可以花费一些代价对这个整数进行变换。

小蓝可以花费 1 的代价将整数增加 1 。

小蓝可以花费 3 的代价将整数增加一个值，这个值是整数的数位中最大的那个（1 到 9）。

小蓝可以花费 10 的代价将整数变为原来的 2 倍。

例如，如果整数为 16，花费 3 将整数变为 22 。

又如，如果整数为 22，花费 1 将整数变为 23 。

又如，如果整数为 23，花费 10 将整数变为 46 。

请问，如果要将整数从初始值 1 变为 整数n，请问最少需要多少代价？

输入格式：

一个整数，作为n的值

输出格式：

输出一个整数，表示最大价值。

输入样例:

2024

输出样例：

79

2.分析:

本题的目标是找到将整数从1变换到2024的最小代价。然后我们可以发现操作和代价为：增加1：花费1的代价。增加数位中最大的值（1到9）：花费3的代价。翻倍：花费10的代价。

状态定义：令dp[n]表示将整数从1变换到n的最小代价。

状态转移方程：

增加1：对于任何n，我们可以通过n-1增加1得到，代价为dp[n] = dp[n-1] + 1。

翻倍：如果n是偶数，我们可以通过n/2翻倍得到，代价为dp[n] = dp[n/2] + 10。

增加最大数位：我们可以找到n的最大数位d，然后通过n-d增加最大数位得到，代价为dp[n] = dp[n-d] + 3。

初始条件和边界：

dp[1] = 0，因为初始值就是1，不需要任何代价。

目标状态：

求dp[n]的值。

算法的步骤：

初始化: 创建一个长度为n+1的dp数组，dp[i]表示将1变成i的最小代价，初始化为无穷大，dp[1] = 0。

遍历每个数: 遍历从1到n，对于每个数i，尝试三种操作。

加1操作: 若i + 1 <= n，更新dp[i + 1]为min(dp[i + 1], dp[i] + 1)。

加最大数位操作: 计算当前数i的最大数位max_digit，若i + max_digit <= y，更新dp[i + max_digit]。

乘2操作: 若i * 2 <= n，更新dp[i * 2]为min(dp[i * 2], dp[i] + 10)。

返回结果: 最终返回dp[n]，即将1变为n的最小代价。

3.代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = minCost(n);
        System.out.println(result);
    }

    public static int minCost(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);     // 初始化为无穷大
        dp[1] = 0;  // dp[1]表示将整数1变为1的最小代价，为0
        for (int i = 1; i <= n; i++) { 
            if (i + 1 <= n) {                    // 加1
                dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
            }
                // 加最大数位
            int maxDigit = getMaxDigit(i); // 找到当前数的最大数位
            if (i + maxDigit <= n) {
                dp[i + maxDigit] = Math.min(dp[i + maxDigit], dp[i] + 3);
            }
                // 乘以2
            if (i * 2 <= n) {
                dp[i * 2] = Math.min(dp[i * 2], dp[i] + 10);
            }
        }
        return dp[n];
    }

    private static int getMaxDigit(int i) {
        int max = 0;
        int temp = i;
        while (temp > 0) {
            max = Math.max(max, temp % 10);
            temp /= 10;
        }
        return max;
    }
}