[プログラマー-evel 3]おつり

完全な問題の説明

問題の概要

あなたが探している金額nとあなたが今持っているお金の種類moneyをパラメータとしてあげると、n元を探す方法の数を求めます.
せいげんじょうけん

nは100000以下の自然数です.

通貨単位は100種類以下です.

すべての通貨が無限であると仮定します.

正解が大きくなる可能性がありますので、100000007を返してください.

答えの数として分類できる

これは典型的なdp問題であり、与えられたお金の種類が金額nに組み合わせることができる場合である.
お金の種類は{100,200,400,600}と同じだと仮定します.与えられた通貨が任意の金額のnを生成できる場合、600元が0回使用される数から600元がi回使用される数(0<=i<=n/600)までである.
それぞれの場合、600元が0次であれば、1つの数字(残りの通貨{100、200、400}がnを構成できる場合)を求める必要があり、i次であれば{100、200、400}(n-i*600)を構成することができる.
各ケース(n−i*600を{100,200,400})について、400元をj回(0<=j<=n/400)と書くと、1つの数を求め、k回(0<=k<=n/2000)を書くときの数で割ることができる.

小さい単位から

まず、最小単位でこの問題にアクセスすると、1つのタイプのお金しかないと仮定できます.
1つの通貨が1つしかなく、mony[i]と呼ばれている場合、作成できる金額(0<=amount<=n)の数は1であり、金額がmony[i]で除算されている場合は0である.
最も簡単な場合、通貨[i+1]を追加します.mone[i+1]が追加された場合、mone[i+1]に0回から書き込む金額を考慮して、amountからamount/mone[i+1]回に設定できます.
mone[i+1]は、mone[i]を使用してamount金額全体を構成できる場合と同様に0回、mone[i]を1回使用してamount-mone[i+1]を構成し、mone[i]を2回使用してamount-2*mone[i+1]を構成する数は同じである.
ここで、通貨[i+2]が追加されたとしても、mony[i]とmony[i+1]を考慮して、amount(0<=amount<=n)を構成できる全てのケースの数を求めているので、mony[i+2]が同じように0回書かれていれば、1回書くことになる…amount/mone[i+2]を使用して答えを記入することも考えられます.

これは答えを表す図です.図中の便利な金額は100単位で表示され、通貨の種類は任意に設定されています.各矢印は、対応するセルの値を計算するために参照する必要があるセルを指します.指定した通貨の倍数を容易にできるセルにのみ表示されますが、実際には各行のすべての列について同じタイプの計算が行われます.
1つの非効率な点は、各グリッドが新しい通貨mony[i]を0からamount/mony[i]に入れるプロセスをシミュレートすることである.
図に{100300}元のみを考慮して600元の計算を作成できる場合は、計算の部分が繰り返し計算されることに注意してください.(図中の2行目7列目)
作成された600元(100元で作成された0元のみ)の数で、2つの300元が含まれます.600元が作成された場合、300元が含まれます(100元の300元のみが作成された場合、2行目の4列目に数値の和が見つかりました.再取得が必要な部分は、0回の300元で600元が作成されたときの数値(100元で600元が作成されたときの数値のみ、1行目の7列目).
したがって、mony[0]からmony[i]までamountを構成できることを考慮すると、この数はdp[i][amount]として表され、図中のテーブルと同様に、構成するamountが現在考慮されている通貨mony[i]以上である場合に表される.money[i]を0回使用してamountを構成できる場合は、数字dp[i-1][amount]とmony[i]を1回からamount/mone[i]回使用して評価し、数字の和dp[i]amount-mone[i]を加算するだけです.

100000*100*4バイトの配列を作成したくない場合は、2 D配列を宣言するのではなく、1 D配列を使用して問題を解決できます.計算の重複はこの問題を解決するのに十分ですが、金額は最大100000に達し、通貨の種類は最大100です.最終的に、dp[i][j]の計算値は、dp[i-1][j]+dp[i]j-mone[i]である.
通貨タイプ別に列を並べずに1行の配列だけを書く場合は、dp[j]値を更新する前に、2 D配列のdp[i-1][j]を持つことになります.
dp[j]+=dp[j-mone[i]を求めると、2次元配列を使用する場合と同じ値が得られます.

コード#コード#

import java.util.*;
class Solution {
    public int solution(int n, int[] money) {
        int mod = 1_000_000_007;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int m : money){
            for(int amount = 0; amount <= n; amount++){
                if(amount >= m){
                    dp[amount] += dp[amount - m];
                    dp[amount] %= mod;
                }
            }
        }
        return dp[n];
    }
}