Как улучшить целочисленное разбиение с n, m, k

Question

моя программа считает целочисленные разделы n, которые имеют k отдельных элементов раздела, каждый из которых меньше или равен m. Как я могу улучшить производительность? Я уже кеширую немедленные результаты.

public long q(int n, int m, int k){
  return q1(n,m,k,0,0,new HashMap());
}

private long q1(int n, int m, int k, int level, int last, Map<String, Long> cache){
  if(n <0){
    return 0;
  }
  if(level+1 ==k){
    if(n >m){
      return 0;
    } else {
      return 1;
    }
  }
  int first = (level == 0) ? 1 : last+1;

  long total = 0;

  for(int i = first; i<= Math.min(m, n/2); i++){
    last = i;

    if ( n - i > 0 && last < n-i) {
      String key = n-i+"_"+level+1+"_"+last;

      Long fetched = cache.get(key);

      if(fetched ==null){
        fetched = q1(n-i,m,k,level+1,last, cache);
        cache.put(key, fetched);
      }
      total += fetched;
    }
  return total;
}