\(DP[i][j]\) を、\(m\leq i\) なる \(m\) まで位置を決めて、あと \(j\) 箇所余っているときの通り数、とすると、combinationを使って素直にDPができます。計算量は \(O(NM^2)\) です。