アットコーダedpc、m問題、pythonで解くときの処理効率化

Question

問題
https://atcoder.jp/contests/dp/tasks/dp_m

解説を見ると、累積和で解く、ということで、計算量はO(NK)となっていますが、
この計算量ではpythonを使って解くと入力例4ですらTLEになってしまいます。
下記が累積和を使って書いたコードです。

import numpy

#入力の取得
f1 = open(r"C:\tmp\input4.txt")
f2,f3 = f1.readlines()
n = int(f2.split()[0])
k = int(f2.split()[1])
a = list(map(int,f3.split()))
mod = 10**9 + 7

#dpは2次元配列
#dp[i][j]→i人目まで（0-Indexed）の子供たちにj個の飴を配る時の、場合の数
dp = [[0]*(k+1) for i in range(n)]

#初期値
#1人の子供にx個の飴を配る場合の数→それぞれ1通り
for i in range(a[0]+1):
    dp[0][i] = 1

for i in range(1,n):
    for j in range(k+1):
        #累積和、最初は0
        s = numpy.cumsum(dp[i-1]).tolist()
        s.insert(0, 0)
        dp[i][j] = (s[j+1] - s[max(0,j-a[i])])%mod
print(dp[n-1][k])

上のコードは計算量O(NK)であってますか？
また、他の方のコードを拝見しますと、

mod = 10**9+7
import numpy as np
f1 = open(r"C:\tmp\input1.txt")
f2,f3 = f1.readlines()
n, k = map(int,f2.split())
A = tuple(map(int, f3.split()))
dp = np.zeros(k+1, np.int64)
dp[0] = 1
for a in A:
    dp[a+1:] -= dp[:-(a+1)]
    dp = dp.cumsum()
    dp %= mod
print(dp[k])

となっており、入力例1で処理を追ってみると、
初期値dp=[1,0,0,0,0]と、子供iに配るmaxの個数の配列A=[1,2,3]があって、
dpをA[0]分ずらして引き算して、累積和を取る、ということをしています。
だからdpは下記の通り推移しまして、
dp=[1,0,0,0,0]
↓
dp=[1,1,0,0,0]
↓
dp=[1,2,2,1,0]
↓
dp=[1,3,5,6,5]
最終的なdpは解答に必要な、私のコードで言うdp[2]の列に等しくなっています。
このコードだとpythonでも時間切れにならずに通りますが、
このコードの計算量はO(NK)ですか？

このコードに至る考え方をご教示ください。

Answer 1

下記が累積和を使って書いたコードです。
上のコードは計算量O(NK)であってますか？

いいえ、O(NK^2)です。
s = numpy.cumsum(dp[i-1]).tolist()もs.insert(0, 0)もO(K)です。
これらが N x K回のループ内で実行されるので、O(NK^2)となります。
これらの処理は、jに依存しないので、jのループの外に出せばO(NK)になります。

このコードだとpythonでも時間切れにならずに通りますが、
このコードの計算量はO(NK)ですか？

はい、O(NK)です。

このコードに至る考え方をご教示ください。

累積和と引き算の順番が逆なだけで、同じことをやっているのですが、どこがわからないのでしょうか。