Q:

Formulating dp problem [Codeforces 414 B]

all here is the problem statement from an old contest on codeforces

A sequence of l integers b 1, b 2, ..., b l (1 ≤ b 1 ≤ b 2 ≤ ... ≤ b
l ≤ n) is called good if each number divides (without a remainder) by
the next number in the sequence. More formally  for all i
(1 ≤ i ≤ l - 1).
Given n and k find the number of good sequences of length k. As the
answer can be rather large print it modulo 1000000007 (109 + 7).

I have formulated my dp[i][j] as the number of good sequences of length i which ends with the jth number, and the transition table as the following pseudocode
dp[k][n] = 
  for each factor of n as i do
    for j from 1 to k - 1
      dp[k][n] += dp[j][i]
    end
  end

But in the editorial it is given as
Lets define dp[i][j] as number of good sequences of length i that ends in j.

Let's denote divisors of j by x1, x2, ..., xl. Then dp[i][j] = sigma dp[i - 1][xr]

But in my understanding, we need two sigmas, one for the divisors and the other for length. Please help me correct my understanding.
My code ->
MOD = 10 ** 9 + 7

N, K = map(int, input().split())

dp = [[0 for _ in range(N + 1)] for _ in range(K + 1)]

for k in range(1, K + 1):
    for n in range(1, N + 1):
        c = 1
        for i in range(1, n):
            if n % i != 0:
                continue
            for j in range(1, k):
                c += dp[j][i]
        dp[k][n] = c

c = 0
for i in range(1, N + 1):
    c = (c + dp[K][i]) % MOD
print(c)

Link to the problem: https://codeforces.com/problemset/problem/414/B

A:

So let's define dp[i][j] as the number of good sequences of length exactly i and which ends with a value j as its last element.
Now, dp[i][j] = Sum(dp[i-1][x]) for all x s.t. x is a divisor of i. Note that x can be equal to j itself.
This is true because if there is some sequence of length i-1 which we have already found that ends with some value x, then we can simply add j to its end and form a new sequence which satisfies all the conditions.
I guess your confusion is with the length. The thing is that since our current length is i, we can add j to the end of a sequence only if its length is i-1, we cannot iterate over other lengths.
Hope this is clear.

