CodeIQ:「キャンディ・アンド・チョコレート」問題の解答

Kawazoe(@riverplus)さんのCodeIQの問題です。
問題とテストケースはこちらにお世話になりました。解答もあります。
->https://blog.goo.ne.jp/r-de-r/e/028d5b79af2afff7dc2ca78b59912f30
こちらにも情報があります。
https://togetter.com/li/1133526
問題自体は難しくないですがちょっとした仕掛に気づくや否やということでしょう。

効率はともかくいろいろな再帰が書けそうです。メモ化が必要です。
まずJuliaです。
F(n,k)=f(n-k,k)はk個のグループがi組(i<=div(n,k))あるときの場合の数を
残りのキャンデーの組み合わせの数f(n-i*k,k-1))で計算しそれらを合計します。
但し、途中n<kとなることがありますので、0=<iとし、
最初にf(n,k)（i>=1)をf(n-k,k)(i>=0)として補正しています。
G(n,k)=g(n-k,k)はまずk個のどのグループにも最低一個はあるので
それを除いています。
更にg(n0,k)はn0個をi個のグループ（0<=i<=min(n0,k))に分ける場合の数を
g(n0-i,i)で再帰的に計算しそれらを合計します。

#Julia ver 1.41,1.53,1.10.3

function f35(n,k,a)
　function solve(n0,k0)
    function f(n,k)
        if n == 0   ||  k == 1
            return 1
        else
            if haskey(dic1,(n,k))
                sum =  dic1[(n,k)]
            else
                sum = 0
                for i in 0 : div(n,k)
                    sum += f(n-i*k,k-1)
                end
                dic1[(n,k)] = sum
            end
            return sum
        end
    end
    function g(n,k)
        if k == 0
            if n == 0
                return 1
            else
                return 0
            end
        else
            if haskey(dic2,(n,k))
                sum = dic2[(n,k)]
            else
                sum = 0
                for i in 0 : min(k,n)
                sum += g(n-i,i)
                end
                dic2[(n,k)] = sum
            end
            return sum
        end
    end
    dic1 = Dict()
    dic2 = Dict()
    return g(n0-k,k) + f(n0-k0,k0)
 end
 x = solve(n,k)
   s = a == x ? "ok " : "no "
   println(s,x)
end

f35(20, 7,164)
f35(35, 7, 2734)
f35(55, 45, 84)
f35(60, 10, 125480)
f35(98, 40, 1428016)
f35(100, 18, 22175656)

Prologでも書きました。
F(N,K)はNから最大のグループの(必ず存在する)K個を除いたN0=N-K個の組み合わせを
まだ一つ以上K個のグループがあるf(N-K,K,F,R1)とそれ以外のf(N,K-1,F,R2)にわけ
合計します。
チョコレートの分け方の場合、グループ内の個数の最小値がMの時の場合の数は
M個除いた残りを最小値がM以上のK-1のグループに分ける場合の数で表せます。
これをg(N-M,K-1,M,G,R1)としg(N,K,M+1,G,R2),g(N,K,M,G,R),R=R1+R2とすると
G(N,K)=g(N,K,1,G,R)で再帰的に1<=M<=div(N,K)のすべての場合の合計がでます。

%swi-Prolog ver 7.4.2,7.6.4,9.2.5
%:-initialization(start).
% start.

twoar(_,0,_).         % two dimension array
twoar(F,X,Y):-arg(X,F,V),functor(V,y,Y),X1 is X-1,twoar(F,X1,Y).
data(F,X,Y,V):-arg(X,F,V1),arg(Y,V1,V).
triar(_,0,_,_).       %　three dimension array
triar(F,X,Y,Z):-functor(V,z,Z),twoar(V,Z,Z),arg(X,F,V),X1 is X-1,triar(F,X1,Y,Z).
data(F,X,Y,Z,V):-arg(X,F,V1),arg(Y,V1,V2),arg(Z,V2,V).


f(N,K,_,1):-(N=:=0;K=:=1),!.
f(N,K,_,0):-(N<0;K<1),!.
f(N,2,_,R):-R is N div 2 + 1.
f(N,K,F,R):-
    data(F,N,K,V),number(V),R=V,!.
f(N,K,F,R):-
    N1 is N-K,K1 is K-1,f(N1,K,F,R1),f(N,K1,F,R2),R is R1+R2,data(F,N,K,R),!.

g(N,0,_,_,R):-(N=:=0->R=1;R=0),!.
g(N,K,M,_,0):-N<K*M,!.
g(N,K,M,G,R):-
    data(G,N,K,M,V),number(V),R=V,!.
g(N,K,M,G,R):-
    N1 is N-M,K1 is K-1,M1 is M+1,g(N1,K1,M,G,R1),g(N,K,M1,G,R2),
    R is R1+R2,data(G,N,K,M,R).
solve35(N,K,R):-
    functor(G,x,N),triar(G,N,K,N),g(N,K,1,G,R1),N1 is N-K,
    functor(F,y,N1),twoar(F,N1,K),f(N1,K,F,R2),R is R1+R2,!.
    
start:-f35(N,K,A),(solve35(N,K,R)->(R==A->Str=" ok  ";Str=" no  ");
    write(fail)),write(" "),write(Str),writeln(R),fail.
start.

f35(20, 7,164).
f35(35, 7, 2734).
f35(55, 45, 84).
f35(60, 10, 125480).
f35(98, 40, 1428016).
f35(100, 18, 22175656).

なおキャンディーの二番目以降のグループのキャンディを
最初のグループのk個の上に次々重ねると、
チョコレートのグループと同じになり,場合の数が同じとなります。