【Atcoder】DPまとめコンテスト M candies #C++

こんばんは
今日はDPまとめコンテストのM candiesを解いてみようと思います！

問題概要

N人の子供たちにK個のあめを配る。ただし子供iに配るあめは0以上a_i個でないといけない。

解法

i人目までの子供にj個のあめを配ることを考え、この場合の数をdp[i][j]とする。
この状態にi-1人目の状態から至るためには、以下からの遷移が考えられる。

i-1人目までにj個配る。i人目には0個配る。
i-1人目までにj-1個配る。i人目には1個配る。
i-1人目までにj-2個配る。i人目には2個配る。
（中略）
i-1人目までにj-a_i-1個配る。i人目にはa_i-1個配る。

数式にすると

$ dp[i][j] = dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]+\cdots+ dp[i-1][j-a_{i-1}] \tag{1} $

式が長い！
このjにj-1を代入して書き換えます。

$ dp[i][j-1] = dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+\cdots+ dp[i-1][j-a_{i-1}-1] \tag{2} $

(1)から(2)を引くとスッキリ。

$$dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-a_{i-1}-1]$$

実装

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
typedef long long ll;
int n,k;
vector<ll> a;
ll dp[110][100010];
ll mod = 1000000007;

int main(){
 cin >> n >> k;
 a.resize(n);
 for(int i = 0; i < n; ++i) cin >> a[i];
 for(int i = 0; i <= n; ++i) dp[i][0] = 1; //i人目までに0個配る方法は1通り

 for(int i = 1; i <= n; ++i){
   for(int j = 1; j <= k; ++j){
     dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%mod;
     if(j - a[i - 1] - 1 >= 0){
       dp[i][j] = (dp[i][j] + mod - dp[i - 1][j - a[i - 1] - 1])%mod;
     }
   }
 }
 cout << dp[n][k] << endl;
 return 0;
}

DPは奥が深いですね