Идеи динамического программирования: одномерные задачи, часть 2

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

В первой части статьи мы разобрали несколько типичных задач динамического программирования с использованием одномерного массива для хранения подзадач.

Идеи динамического программирования: одномерные задачи, часть 1

tproger.ru

В этой статье продолжим рассмотрение подобных задач.

Вернемся к кузнечику, который прыгал по кувшинкам в первой статье.

Кузнечик, кувшинки и монетки

В этой задаче на кувшинки добавляются монетки, причём их можно как собирать, так и терять. Теперь нам неважно, каким путем двигается кузнечик, главное — собрать максимальное количество монеток к последней кувшинке.

Немного изменим условия прыжков. Теперь кузнечик может прыгать на 1, 2 или 3 кувшинки вперёд. Также кузнечик не может терять больше монеток, чем у него есть в наличии.

Как мы уже знаем, две самые главные вещи в динамическом программировании — начальные значения и переход от одной подзадачи к другой. Давайте посмотрим, что у нас является подзадачей, т.е. какие значения будем хранить.

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

Рассмотрим пятую кувшинку, на которой мы теряем 3 монетки. Откуда мы можем прыгнуть на неё? Со второй, третьей или четвёртой кувшинки. Откуда мы должны прыгнуть на неё, чтобы заработать максимальное количество монеток? С кувшинки, на которой наше заработанное количество монеток было максимальным. Это будет выглядеть примерно так:

			// иcходный массив, с монетками на кувшинках
const coins = [4, -2, 1, -1, -3];

// массив, хранящий максимальное количество монет
// при достижении i кувшинки
const maxCoins = [4, 2, 5, 4];

// в четвёртой позиции массива хранится информация про пятую кувшинку
maxCoins[4] = Math.max(maxCoins[1], maxCoins[2], maxCoins[3]) + coins[4];

Подумаем над начальным значением. Мы можем через несколько if’ов посчитать, сколько будет на каждой из кувшинок заработано монеток. Но если в данном случае это будет довольно просто, то, например, если кузнечик сможет прыгать на 10 кувшинок, то это приведёт к очень сложному и запутанному коду. Попробуем обойтись без начальных значений, а предыдущие значения, если они выходят за границы массива, игнорировать.

			const getMaxCoins = (coins) => {
  // максимальное количество монет на каждой из кувшинок
  const maxCoins = [];

  // начинаем заполнение с нулевого элемента, т.е. с первой кувшинки
  // без начальных значений
  for (let i = 0; i < coins.length; i++) {
    // максимальное количество монеток, которое можно заработать
    // на предыдущих кувшинках, с которых мы можем прыгнуть на текущую
    const previousMaxCoins = [];

    // можно эти проверки выполнять в цикле
    // для первых 3-х элементов coins, массив previousMaxCoins
    // будет содержать не 3 элемента, а меньше, для остальных - 3
    if (i - 3 >= 0) previousMaxCoins.push(maxCoins[i - 3]);
    if (i - 2 >= 0) previousMaxCoins.push(maxCoins[i - 2]);
    if (i - 1 >= 0) previousMaxCoins.push(maxCoins[i - 1]);

    // количество монет на текущей кувшинке 
    // плюс в следующем if, 
    // добавляется максимальное значение с предыдущей кувшинки
    let maxCoinsInIPosition = coins[i];

    // проверка для нулевого элемента
    // когда массив previousMaxCoins будет пустой
    // и Math.max(...[]) вернет -Infinity
    if (previousMaxCoins.length > 0) {
      maxCoinsInIPosition += Math.max(...previousMaxCoins);
    }

    // здесь проверяем условие, чтобы у кузнечика
    // не было отрицательное количество монеток
    // можно было вот так 
    // maxCoinsInIPosition = Math.max(maxCoinsInIPosition, 0);
    maxCoinsInIPosition = maxCoinsInIPosition < 0 ? 0 : maxCoinsInIPosition;
    
    maxCoins.push(maxCoinsInIPosition);
  }

  // в 0 элементе хранится значение для первой кувшинки
  // массив заполнен на maxCoins.length значений
  // от 0 до maxCoins.length
  return maxCoins[maxCoins.length - 1];
}

console.log(getMaxCoins([4, -2, 1, -1, -3]));

В примере с распределение монеток [4, -2, 1, -1, -3] максимальная сумма будет 2. Кузнечик прыгнет на первую, третью и пятую кувшинки. На пятую прыгать обязательно, т.к. это условие задачи — достигнуть последнюю кувшинку.

Путь, чтобы собрать максимум монеток

Дополним задачу — теперь нам нужно не просто найти, сколько максимально можно собрать монет, добравшись до последней кувшинки, а ещё и найти путь, как это было сделано.

Часто в задачах динамического программирования применяется следующая техника: берём наше вычисленное значение, идём от конца к началу массива с описанием максимума на каждой кувшинке (в данном случае maxCoins), восстанавливая обратную последовательность вычислений: будем находить максимальное значение в предыдущих ячейках массива maxCoins.

			const getMaxCoinsPath = (coins) => {
  const maxCoins = [];
  for (let i = 0; i < coins.length; i++) {
    const previousMaxCoins = [];

    if (i - 3 >= 0) previousMaxCoins.push(maxCoins[i - 3]);
    if (i - 2 >= 0) previousMaxCoins.push(maxCoins[i - 2]);
    if (i - 1 >= 0) previousMaxCoins.push(maxCoins[i - 1]);

    let maxCoinsInIPosition = coins[i];
    if (previousMaxCoins.length > 0) {
      maxCoinsInIPosition += Math.max(...previousMaxCoins);
    }

    maxCoinsInIPosition = maxCoinsInIPosition < 0 ? 0 : maxCoinsInIPosition;
    maxCoins.push(maxCoinsInIPosition);
  }

  // до этого момента код тот же, что и в предыдущем примере
  return findPath(maxCoins);
}

const findPath = (maxCoins) => {
  // последняя кувшинка всегда в пути, по условию задачи
  const path = [maxCoins.length - 1];

  let maxCoinsPreviousPosition = maxCoins.length - 1;
  while (maxCoinsPreviousPosition >= 0) {
    // 0 для первых 3-х элементов
    const previousPositionShift =
      maxCoinsPreviousPosition - 3 > 0 ? maxCoinsPreviousPosition - 3 : 0;

    // для текущего примера [-1, -1, 4, -2, 1, -1, -3]
    // диапазон previousPositionShift maxCoinsPreviousPosition
    // будет принимать значения
    // 3 6
    // 1 4
    // 0 2
    // 0 0
    // slice не включает последний элемент, при использовании 0, 0 вернется
    // пустой массив

    // отрезаем предыдущие 3(или меньше) элементов, для поиска максимума
    const previousCoinsValues = maxCoins.slice(
      previousPositionShift,
      maxCoinsPreviousPosition
    );
    
    // когда previousCoinsValues - пустой массив, поиск пути завершен
    if (previousCoinsValues.length === 0) break;
    
    const previousMaxCoinValue = Math.max(...previousCoinsValues);
    
    // если несколько одинаковых значений, то находим только одно из них
    // previousMaxCoinPosition может содержать значение от 0 до 2
    const previousMaxCoinPosition =
      previousCoinsValues.indexOf(previousMaxCoinValue);

    maxCoinsPreviousPosition = previousMaxCoinPosition
      + previousPositionShift;

    path.push(maxCoinsPreviousPosition);
  }

  // искали путь с конца, для окончательного ответа нужно его инвертировать
  return path.reverse();
}

// путь - [0, 2, 4, 6]
console.log(getMaxCoinsPath([-1, -1, 4, -2, 1, -1, -3]));

Также мы можем найти путь другим способом — ввести дополнительную структуру данных и хранить в ней путь, по которому мы добрались до текущей ячейки. Код выглядит немного проще, но при работе с большим объемом данных хранение путей может занимать значительное место в памяти. Посмотрим на решение:

			const getMaxCoinsPath = (coins) => {
  const maxCoins = [];
  for (let i = 0; i < coins.length; i++) {
    const previousMaxCoins = [];

    if (i - 3 >= 0) previousMaxCoins.push(maxCoins[i - 3]);
    if (i - 2 >= 0) previousMaxCoins.push(maxCoins[i - 2]);
    if (i - 1 >= 0) previousMaxCoins.push(maxCoins[i - 1]);

    let maxCoinsInIPosition = coins[i];
    let pathToMaxCoins = null;

    if (i !== 0) {
      // позиция в previousCoins с максимальным количеством монеток
      let maxCoinsPositionInPrevious = 0;
      let maxCoins = previousMaxCoins[0].coins;

      for (let j = 1; j < previousMaxCoins.length; j++) {
        if (maxCoins < previousMaxCoins[j].coins) {
          maxCoins = previousMaxCoins[j].coins;
          maxCoinsPositionInPrevious = j;
        }
      }

      // путь до предыдущего элемента, с набором максимума монеток
      pathToMaxCoins = previousMaxCoins[maxCoinsPositionInPrevious].path;
      
      // в maxCoinsInIPosition исходное значение монеток на кувшинке i
      // coins[i]
      // плюс максимальное значение на предыдущей кувшинке, с которой можем
      // прыгнуть на нее
      maxCoinsInIPosition += maxCoins;
    } else {
      // для первого элемента - пустой путь
      pathToMaxCoins = [];
    }

    maxCoinsInIPosition = maxCoinsInIPosition < 0 ? 0 : maxCoinsInIPosition;
    // добавляем i к пути, для текущего элемента
    maxCoins.push(
      { coins: maxCoinsInIPosition, path: [...pathToMaxCoins, i] }
    );
  }

  // просто возвращаем путь для последнего элемента
  return maxCoins[maxCoins.length - 1].path;
}

// [0, 2, 4, 6]
console.log(getMaxCoinsPath([-1, -1, 4, -2, 1, -1, -3]));

Задача для практики на LeetCode

Наибольшая (по длине) возрастающая подпоследовательность

Подпоследовательность — это любая последовательность внутри массива, расположенная по возрастанию индексов. Например? в массиве [1, 2, 3, 4, 5] набор чисел [1, 3, 5] является подпоследовательностью. [1, 4, 2] не является, т.к. 2 расположена перед 4.

Задача — написать функцию, которая бы возвращала максимальную подпоследовательность.

Рассмотрим массив [1, 5, 3, 6, 4, 5, 2]. Несколько его возрастающих подпоследовательностей: [1, 5, 6], [1, 5], [1, 3], [1, 3, 5], [1, 3, 4, 5]. Наибольшая из всех таких подпоследовательностей размера 4:

Идеи динамического программирования: одномерные задачи, часть 2 1

Для начала посмотрим, как можно решить задачу про максимальную длину такой подпоследовательности. Введём массив, который будет хранить максимальную длину для текущего элемента. Например, для последовательности выше [1, 5, 3, 6, 4, 5, 2] такой массив в конце вычислений будет содержать значения [1, 2, 2, 3, 3, 4, 2]. Назовем его, например, longestSubsequence. Для первого элемента начальное значение очевидно — последовательность, состоящая только из этого элемента. Добавим начальное значение:

			const longestSubsequence = [1];

Для каждого последующего элемента будем искать в исходном массиве значение меньше текущего, проверять, последовательность какой длины можно составить с добавлением текущего элемента, и выбирать максимальную.

Например, мы добрались до элемента 4, longestSubsequence будет содержать в себе [1, 2, 2, 3]. Ищем в исходном массиве элементы, меньше чем 4, это 1 и 3. Длина подпоследовательностей для этих элементов: 1 и 2. Если добавить после 1 число 4, то получим длину последовательности 2: longestSubsequence[0] + 1, если после 3, то длина будет 3: longestSubsequence[2] + 1. Добавляем единицу к longestSubsequence элементу, т.к. добавление нового элемента увеличивает подпоследовательность.

Выяснили начальные значение и как переходить от одной подзадачи к другой, остался вопрос, где брать ответ. Максимальная возрастающая подпоследовательность может закончиться в любом месте исходного массива. Значит, нужно просто найти максимальное значение в массиве longestSubsequence. Посмотрим на решение подзадачи про нахождение длины:

			const lengthOfLongestIncreasingSubsequence = (nums) => {
    // массив, содержащий длину максимальной подпоследовательности
    // в позиции соответствующего элемента,
    // т.е. longestSubsequence[0] соответствует максимальной длине для 
    // nums[0]
    const longestSubsequence = [1];
    
    // 0-й элемент уже обработали через установку начального значения,
    for (let i = 1; i < nums.length; i++) {
        // находим в эту переменную длину максимальной подпоследовательности,
        // в которую можем добавить текущий элемент
        let maxPreviousSubsequence = 0;
        
        // проходим все элементы левее текущего - i элемента
        // находим те, которые меньше текущего значение - nums[i]
        // и находим наибольшую подпоследовательность,
        // предыдущие значения хранятся в longestSubsequence[j]
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i] &&
                longestSubsequence[j] > maxPreviousSubsequence) {
                maxPreviousSubsequence = longestSubsequence[j];
            }
        }
        
        // после обработки очередного элемента,
        // длина подпоследовательности увеличивается на 1
        longestSubsequence.push(maxPreviousSubsequence + 1);
    }
    
    // ответ может быть в любой позиции, и это просто максимальное число
    return Math.max(...longestSubsequence);
};

// максимальная длина - 4
console.log(lengthOfLongestIncreasingSubsequence([1, 5, 3, 6, 4, 5, 2]));

Доработаем задачу, чтобы можно было находить не только длину, но и саму подпоследовательность. Для этого есть два пути. Можем хранить в массиве максимальную подпоследовательность в текущей позиции целиком или просто индекс предыдущего элемента для позиции.

Хранение подпоследовательностей может привести к значительному расходу памяти для больших значений. Рассмотрим решение с хранением индекса предыдущего элемента:

			const getLongestIncreasingSubsequence = (nums) => {
    const longestSubsequenceInPosition = [1];
    const previousIndexOfLongestSubsequence = [-1];
    
    for (let i = 1; i < nums.length; i++) {
        let maxPreviousSubsequence = 0;

        // если внутри следующего for, по предыдущим элементам,
        // не войдем в if ни один раз
        // значит предыдущего элемента нет
        // и надо проставить значение по умолчанию: -1
        previousIndexOfLongestSubsequence[i] = -1;
        
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i] &&
                longestSubsequenceInPosition[j] > maxPreviousSubsequence) {
                maxPreviousSubsequence = longestSubsequenceInPosition[j];
                
                // если вошли в этот if
                // значит в позиции j нужный предыдущий элемент
                previousIndexOfLongestSubsequence[i] = j;
            }
        }
        
        longestSubsequenceInPosition.push(maxPreviousSubsequence + 1);
    }
    
    // для рассматриваемого примера [5, 1, 5, 3, 6, 4, 5, 2]
    // массив с максимальной подпоследовательностью в позиции
    // longestSubsequenceInPosition [1, 1, 2, 2, 3, 3, 4, 2]
    // индекс предыдущего элемента, для максимальной подпоследовательности
    // previousIndexOfLongestSubsequence [-1,-1,1, 1, 2, 3, 5, 1]
    
    const lengthOfLongestSubsequence =
      Math.max(...longestSubsequenceInPosition);
    
    // позиция окончания максимальной подпоследовательности
    const lastIndexOfLongestSubsequence =
      longestSubsequenceInPosition.indexOf(lengthOfLongestSubsequence);

    const longestSubsequence = [];
	let currentElementOfSubsequence = lastIndexOfLongestSubsequence;
	
    // идем по массиву previousIndexOfLongestSubsequence,
    // находя предыдущие элементы,
    // начиная с lastIndexOfLongestSubsequence,
    // когда достигнем -1 значения, то предыдущего элемента нет
    while (currentElementOfSubsequence !== -1) {
        longestSubsequence.push(nums[currentElementOfSubsequence]);
        
        currentElementOfSubsequence =
          previousIndexOfLongestSubsequence[currentElementOfSubsequence];
    }
    
    // массив, как и в предыдущей задаче, инвертирован
    return longestSubsequence.reverse();
};

// максимальная подпоследовательность - [1, 3, 4, 5]
console.log(getLongestIncreasingSubsequence([5, 1, 5, 3, 6, 4, 5, 2]));

Задача для практики на LeetCode

Игра — делители

Рассмотрим ещё одну задачу с сайта Leetcode. Если не быть знакомыми с методами динамического программирования и не понять, что их здесь стоит применять, то решение этой задачи может быть очень сложным.

Есть два игрока, в задаче — Алиса (или Элис) и Боб. Дано число, например, 5. Игроки по очереди уменьшают число следующим действием: находят целочисленный делитель текущего числа (не само число), вычитают его из текущего числа. Так получается следующее число. Первой ходит Алиса.

Цель игры — определить, сможет ли выиграть Алиса при идеальной игре обоих участников. Вернуть true, если сможет.

Рассмотрим случай с числом 5. Ход Алисы. Число 5 имеет 2 делителя: 1 и 5. Но выбрать 5 по условию задачи мы не можем, выбираем единицу. Вычитаем её, получаем число 4 для следующего хода.

Ход Боба. 4 имеет три делителя, мы можем использовать только 1 или 2. Допустим, что используем 1, для Алисы оставляем число 3.

Дальнейшая игра очевидна и не предоставляет выбор для игроков.

Возникает проблема: какое число оптимально использовать, когда есть несколько вариантов делителей? Например, в рассматриваемом случае Боб на втором шаге мог выбрать делитель 1 или 2. Мы могли построить дерево до конца игры, и если у Алисы нет выбора, и в одном из вариантов выиграет Боб, то тот ход был оптимальным. Но что если у Алисы есть выбор, как определить оптимальность?

Рассмотрим игру для числа 6:

У Алисы на первом ходу есть на выбор три числа для вычитания: 1, 2, 3 — целочисленные делители числа 6. У Боба тоже появляется ветвление, если Алиса выбрала число 2 и оставила для Боба число 4. Когда мы дойдём до конца этого дерева, то как определить, были ли все ходы оптимальны? Таким подходом, сверху вниз, эту задачу не решить.

Рассмотрим другой подход, снизу вверх. Будем идти от единицы и выше, постараемся определить, кто выиграл на каждом шаге. Для хранения результатов создадим массив, хранящий возможность выигрыша для того, чей ход текущий.

			const gameResultForStartPlayer = 
  [false, true, false, true, false, true, false, true, false, true];

Например, если у Алисы число 2, то берем первый элемент из этого массива. Он true, значит, Алиса может выиграть. Для числа 5 — false, значит, если оба игрока играют оптимальным способом, то Алиса проиграет. Как же создать такой массив?

Для числа 1 ответ очевиден: Алиса не сможет вычесть из этого числа само себя и сразу проигрывает.

Число 2. Может ли Алиса сделать так, что Боб попадет в ячейку со значением false, т.е. гарантированно проиграет? Да, Алиса может вычесть единицу, для Боба останется число 1, которое проигрывает для того, чей ход. Мы знаем, что число 1 проигрывает для того, кто ходит, т.к. именно эта информация хранится в массиве gameResultForStartPlayer.

Рассмотрим, например, число 9. Массив gameResultForStartPlayer уже должен быть заполнен для всех предыдущих чисел. Сможет ли Алиса сделать такой ход, чтобы Боб проиграл? Целочисленные делители числа 9 — 1 и 3. Бобу достанется либо 8, либо 6. У обоих этих чисел значение в массиве — true, следовательно, при оптимальной игре Боб выиграет. Соответственно, если Алисе достанется число 9, то она проиграет, и при заполнении массива следует в него добавить значение false.

Рассмотрим решение:

			const divisorGame = (n) => {
  // рассмотренный выше массив, для результата на текущем ходе игрока
  const gameResultForStartPlayer = [false];
  
  for (let i = 2; i <= n; i++) {
    let resultOfIGame = false;
    
    // ищем все делители, без оптимизаций - цикла до Math.sqrt(i), например
    for (let divisor = 1; divisor < i; divisor++) {
      // если будет false хотя бы в одной позиции gameResultForStartPlayer,
      // для числа, которое останется противнику,
      // значит оппонент проигрывает
      // и в текущую позицию в gameResultForStartPlayer, добавим true
      if (i % divisor == 0 &&
          gameResultForStartPlayer[i - divisor - 1] == false) {
        resultOfIGame = true;
        break;
      }
    }
    
    gameResultForStartPlayer.push(resultOfIGame);
  }

  // в 0 позиции храним значение для 1 числа, в n-1 для n-го числа
  return gameResultForStartPlayer[n - 1];
};

Заключение

В двух статьях мы рассмотрели основные задачи динамического программирования, которые можно решить, используя одномерный массив. Это наиболее простые примеры этого способа решения задач, разбираясь с которыми, можно понять основные концепции динамического программирования и двигаться дальше.