algorithm - 硬貨の両替、ただし各金種の硬貨は 1 つだけ

Question

問題は：

私が思いついたアルゴリズムは次のようなものです。

pair<bool, bitmask>[n][A] memo;     
// memo[i][j].first will be true if its possible to 
// use up to i-th denomination for amt j
// memo[i][j].second will contain info on which 
// denominations are used
for i = 0 to n:
    for j = 1 to A:
    if (i==j): C[i][j] = {true, {i}}
    else if (C[i-1][j].first == true): C[i][j] = C[i-1][j]]
    else if (...see recurrance relation...): 
        C[i][j] = {true, C[i-1][j]+{denom[i]}}
    else: C[i][j] = false

ここまでは正しいですか？しかし、その正しさをどのように証明できるかわかりません...私の試みは、コードを英語で書き直したように見えます...

第 1 の場合: amt=i を解くために、金種 i の硬貨 1 枚を常に使用できます。最初の場合は、現在の金種を使用せずに amt の解決策がある場合、その解決策を再利用できます。2番目のelse if：現在の金種が使用でき（<= amt）、金種が使用されていない場合、...

複雑さについて: テーブルのサイズは nA です。また、各セルがいっぱいになるまでに O(1) 時間かかります。誰かが私を正しい方向に向けるのを助けることができますか?