0557:A First Grader

メモ化再帰で解いた。

dp[ i ][ j ]:=i番目までの計算結果がjのパターン数

最初が0の時を考えてなかったせいでWA連発した。

#include<iostream>

using namespace std;

typedef long long ll;

ll dp[101][21];
int a[101],n;

ll func(int i, int res){

  if(res<0 || 20<res)return 0;
  if(dp[i][res]>0)return dp[i][res];
  if(i>n-2 && res==a[n-1])return 1;
  else if(i>n-2 && res!=a[n-1])return 0;

  ll ans=0;
  ans+=func(i+1,res+a[i]);
  if(i)ans+=func(i+1,res-a[i]);
  
  return dp[i][res]=ans;
}

int main(void){

  while(cin >> n){
    for(int i=0;i<n;i++)
      cin >> a[i];

    for(int i=0;i<=n;i++)
      for(int j=0;j<21;j++)
	dp[i][j]=0;
    
    cout << func(0,0) << endl;
  }
  return 0;
}