수학 + dp 같은데 감도 못잡겠노


예를 들어 지금 내가 k 를 기준으로 하고 총 길이가 n 일때

1~k-1 , k 는 무조건 있을 테니 남은 자리의 갯수는 n-k 일거임

그럼 이 n-k의 자리를 (1~(k-1))로만 채울건지 

1~k,k+1 를 세워놓고 (n-k-1) 자리를 (1~(k-1)),k+1 로 채울건지.. 쭉 나열했다고 가정까진 했는데


저 n-k 자리를 (1~(k-1)) 를 어떻게 구할건지랑

k가 하나 더 늘어났을 때 중복 처리를 어떻게 할 지 감도 안옴 ㅋㅋ