PowerSum超时测试用例

Question

请需要您的帮助，我得到了一个失败的测试用例，由于超时，如果有人可以帮助我提高代码执行所花费的时间。这个问题来自HackerRank网站，如果有人需要更多的解释，我会在下面的评论中引用这个问题的链接

from itertools import  combinations


def powerSum(X, N,n=1,poss=[]):
    if(n**N <= X):
        poss.append(n)
        n+=1
        rslt = powerSum(X,N,n,poss)
    else:
        tmp=[]
        for _ in range(len(poss)):
            oc=combinations(poss,_+1)
            for x in oc:
                ok = sum([num**N for num in x])
                if(ok == X):    
                    tmp.append(ok)
        return len(tmp)
    return rslt

Answer 1

我不擅长python，但我希望下面的java代码可以很容易理解，这是一个间接的子集和问题的变体，这是一个动态规划问题，在给定值数组的情况下，您必须找到很多方法来获得给定的特定和，所以基本上在应用子集问题之前，我已经列出了一个数字列表，可以通过在第k次方超过x的数字处停止来计算所需的总和，因为从该自然数开始，进一步的自然数将有更大的第k次方值，因此不需要将它们保留在我们的列表中，因此这里是一个动态规划问题，如上所述，其中我们的列表具有有效自然数的第k次方值，我们必须找到不同的方法，使用这些第k次方值来获得和x

下面是更清晰理解的代码

import java.util.*;

public class Main {
    public static int find_it(int x , int n , List<Integer> a , int [][] dp){

        for(int i = 0; i < n; ++i){
            dp[i][0] = 1;
        }
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= x; ++j){       
                dp[i][j] += dp[i - 1][j];
                if(j - a.get(i - 1) >= 0){
                    dp[i][j] += dp[i - 1][j - a.get(i - 1)];
                }
            }
        }
        return dp[n][x];    
    }
    public static void main(String [] args){

        Scanner input = new Scanner(System.in);
        int x = input.nextInt() , k = input.nextInt();
        List<Integer> a = new ArrayList<>();
        for(int i = 1; ; ++i){
            double value = Math.pow(i , k);
            if(value > x){
                break;
            }
            a.add((int)value);
        }
        int n = a.size();
        int [][]dp = new int[n + 1][x + 1];
        int answer = find_it(x , n , a , dp);
        System.out.println(answer);
        input.close();
    }
}