幸运机票(计数幸运数字量,具有的所有的数字指定的总和)
-
25-09-2019 - |
题
下面是问题
您给出数字1≤N≤50.每个票都有2N位数字。我们把票幸运的,如果它的前N个数字之和等于其最后N个数字的总和。同时,也给出在号码的所有数字的总和。你的任务是计数幸运数字量,具有的所有的数字指定的总和。
有关输入2 2输出为4(0101,0110,1001,1010)
你能帮我解决这个问题呢?什么是最低的复杂性?
解决方案
如果需要的总和是s
,则每一半必须具有总和s/2
。现在,你需要找到f(n, s/2)
:许多正位数怎么有位s/2
的总和。知道f(n, s/2)
,就可以得到答案在一条线(试计算出来自己)。
至于如何计算f(n, m)
:这是标准的DP。你有递推公式一样f(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2) + ... + f(n-1, m-9)
。在这里,0, 1, 2, .. 9
对于给定数量的最后一位所有可能的选择。如果最后的数字是k
,那么剩下的就是以数字(n-1)
的总和m - k
长数量。
希望它帮助。
PS根据问题的制约,你需要某种形式的长期算术来传递它。
其他提示
private static boolean isLucky(int n) {
int sum1 = 0;
int sum2 =0;
String s = String.valueOf(n);
System.out.println("After Conversion in String= " + s);
for (int i = 0; i < (s.length()) / 2; i++) {
System.out.println("half string === " + s.charAt(i));
sum1 = sum1 + Character.getNumericValue(s.charAt(i));
}
System.out.println("half sum === " + sum1);
for(int j=(s.length()) / 2 ; j< s.length();j++){
System.out.println("half string === " + s.charAt(j));
sum2 = sum2 + Character.getNumericValue(s.charAt(j));
}
System.out.println("another half sum === " + sum2);
if(sum1 == sum2){
return true;
}
return false;
}
不隶属于 StackOverflow