Оптимизация задачи раскраски индекса с одним соседним цветом разрешена

Я столкнулся с этой проблемой окраски индекса (не совсем типичной проблемой m-раскраски графа), которую я пытался решить с помощью поиска с возвратом, но решение работает должным образом только для тестовых случаев с меньшим значением и терпит неудачу для более крупных из-за экспоненциальной временной сложности.

Как его оптимизировать, чтобы он не выполнялся в экспоненциальное время. Есть ли подход DP для решения этой проблемы?

Постановка задачи:

Вам даны 3 переменные: n, k, x

n -> количество индексов, которые нужно раскрасить

k -> Доступное количество цветов -> 1,2,3,...K

x -> Идентификатор цвета, который можно использовать для окрашивания двух соседних индексов.

Вы должны раскрасить n индексов, расположенных по оси X, в k цветов так, чтобы никакие два соседних индекса не были одного цвета. Однако вам также дается x, который является идентификатором цвета, что является исключением из приведенного выше правила, поэтому разрешено иметь два соседних узла с цветом = идентификатором цвета.

Вы должны найти общее количество способов, которыми можно раскрасить все индексы, следуя приведенным выше правилам.

Пример. Для n = 3 k = 2 x = 1 : Все возможные решения: (1,1,1), (1,1,2), (1,2,1), (2,1,1), ( 2,1,2)

Ниже приведено мое решение.

public class ColoringIndices {
    public static void main(String[] args) {
        int n = 17;
        int k = 4;
        int x = 3;
        placeColors(n, k, x);
    }

    static int count = 0;

    private static void placeColors(int n, int k, int x) {
        int currpos = 0;
        int[] arr = new int[n];
        placeColorsUtil(n, k, x, currpos, arr);
        System.out.println(count % 1000000007);
        count = 0;
    }

    private static void placeColorsUtil(int n, int k, int x, int currpos, int[] arr) {
        if(currpos == n){
            int mod = 1000000007;
            count = count % mod;
            count++;
            return;
        }

        for (int colorId = 1; colorId <= k; colorId++) {
            if (isSafe(colorId, currpos, arr, x)) {
                arr[currpos] = colorId;
                placeColorsUtil(n, k, x, currpos + 1, arr);
            }
        }
    }

    private static boolean isSafe(int colorId, int currpos, int[] arr, int x) {
        if (currpos < arr.length && currpos > 0) {
            if (colorId != x && arr[currpos - 1] == colorId) {
                return false;
            }
        }
        return true;
    }
}