557. A First Grader

問題

N個の数字が与えられ、N-1個の数字の間には＋または-がはいり、その計算結果がN番目の数字になるような計算を考える。
前方から＋または-で計算して、負の数または20を超える途中計算になるような計算が許されない場合、何通りの計算方法があるか？を答える。

N<=100

考え方

dp[i][j]:=i番目までの数字を計算して、結果がjになるパターン数
として考えると、今、i番目まで計算して答えがjになっている場合、＋として計算するならばdp[i+1][j+(i+1)番目の数字]へ、-として計算するならばdp[i+1][j-(i+1)番目の数字]になることができるので、dp[i][j]をそこへ加算していけば求められる。