算法中的时限超过误差
我想转换一个可除数为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这个输出，我的代码在特定时间内无法计算
如何改进我的算法？
回答 2
Stack Overflow用户
发布于 2015-01-24 18:45:46
这就是我如何解决这个问题的方法:您需要一个dpPS数组，其中dpik指定您在数字表示中的位置为i，您有j金额，到目前为止的总和是k。基本思想是，如果你改变(或不)一个数字，这个问题减少到一个子问题(左数字，左钱，总和)，每个数字最多有10个选项，所以要填补每一个状态，你将需要一个循环10。因此，时间复杂性O(P *C*S* 10)。由于N在最大P=19 (数字)处仅为最大10^18，C=200 (如您所述)和S在最大值为9*18 (数字之和)。因此，该算法对于给定的时间约束和内存是合适的，即O(P *C* S)。
因此，除了递归的逻辑之外，您还需要使用回忆录(为已经访问的状态存储答案)和递归。
Stack Overflow用户
发布于 2015-01-24 18:47:39
对于这样的问题，使用递归来生成所有的可能性会导致所花费的时间随着输入的大小呈指数增长。如果您想要一种快速实现大输入大小的算法，您最好考虑一种方法来计算它，而不产生所有的可能性。
您可能需要这样一个事实:一个数字的数字之和可以被3除，也可以被3整除。
所以，也许看看你原来数字的数字之和给出的是什么模3。例如，如果它是1，你所做的数字值的总变化将需要2模3。然后你可以从那里前进。
https://stackoverflow.com/questions/28128711
复制相似问题
腾讯云开发者
