aoj0097:Sum of integers II

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0097

解法

まず、この問題は以下の問題の制約強化ver.です。lattemalta.hatenablog.jp

今回も同じ方針で解いていきます。具体的には、0から100までの101個の数字それぞれについて足すか足さないかを決めます。その結果条件を満たしていれば数え上げる。ただしこのままではくらいの時間になって地球が終わります。

そこで、再帰をメモ化します。実はくらいの枝分かれをする再帰ではかなりの部分は既に一度計算した値を再計算しています（何度も同じ引数の組で関数が呼ばれている）。具体的には、メモ化用の配列を用意しておいて、最初はまだ計算していないことを示す数字で初期化しておく（今回は-1で初期化した。組み合わせは負にはならないので）。そして、ある引数の組に対して計算を行ったらメモ化配列にその値を格納しておく。再度その引数の組で関数が呼び出された場合は計算を行わずにメモ化配列に格納された値を返す。このような工夫をすると、それぞれの引数の組に対して1度しか計算が行われなくなります。

今回の問題では引数の組み合わせは大体通りなので、計算は高々回程度しか行われないことがわかります。よってACします。

ちなみに、メモ化配列を再帰ではなくforループで埋めていく手法もあります（動的計画法,dpとも）。この問題の場合はdpのほうが多分楽です。

コード

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[101][10][1001];

int n,s;

int dfs(int now,int k,int t){
    if(t<0||k<0)return 0;
    if(now<0){
        if(!k&&!t)return 1;
        else return 0;
    }
    if(~dp[now][k][t])return dp[now][k][t];

    int ret=dfs(now-1,k,t)+dfs(now-1,k-1,t-now);
    return dp[now][k][t]=ret;
}
signed main(){
    fill_n(**dp,101*10*1001,-1);
    while(cin>>n>>s,n||s)cout<<dfs(100,n,s)<<endl;
    return 0;
}