Учитывая строку длины n, я всегда использую массив n+1 длины для динамического программирования.
n
n+1
В этом случае, если я скажу, что это O(n) [вместо O(n+1)] это будет неточно?
O(n)
O(n+1)