java - 算法中超过时间限制错误

Question

我想转换一个能被 3 整除的数字

一个数字可以转换为具有相同位数且没有前导零的其他数字。

将一个数字转换为其他数字的成本是相应数字的绝对差之和。例如，将 235 转换为 331 的成本为 5(因为相应数字的绝对差为 |3−2|+|3−3|+|1−5| ，即 |1|+0+|−4| =5。

Number= 66  cost= 3

在66的成本≤3内可以创造的数字是36,45,54,57,63,66,69,75,78,87,96。所以答案是 11。

我的方法:
我将输入作为字符串，并且 使用递归调用进行所有组合

public static void cal(int len , int sum , int c , String SS){

    if(c>cost) return ;
    if(len==SS.length()){
        if(sum%3==0) ans++;
        return;
    }

    for(int i=0;i<=9;i++){
        int xx =Math.abs(i-Character.getNumericValue(SS.charAt(len)));
        cal(current+1, len+1, sum+i, c+xx, SS);
    }
}

因为 MSB 不允许零。

 for(int i=1;i<=9;i++){
     int xx =Math.abs(i-Character.getNumericValue(SS.charAt(0)));
     cal(i, 1, i, xx , SS);
 }

例如 237946732463272737 60 这个输出我的代码无法在特定时间内计算

我如何改进我的算法

Answer 1

这就是我解决问题的方法:你需要一个 dp[P][C][S] 数组，其中 dp[i][j][k]指定你在数字的数字表示中的位置 i，你有 j 金额，到目前为止的总和是 k . 基本思想是，如果您更改(或不更改)一个数字，问题将减少为(左数字、左钱、总和)的子问题，每个数字最多有 10 个选项，因此要填充每个状态，您需要一个 10 的循环.所以时间复杂度O(P * C * S * 10)。由于 N 最大为 10^18，最大 P=19(数字)，C=200(如您所述)，S 最大为 9*18(数字总和)。因此，对于给定的时间限制以及 O(P * C * S) 的内存，该算法是不错的。
因此，除了递归逻辑之外，您还需要使用内存(存储已访问状态的答案)和递归。