Задача укладки плиток для создания стабильного стека

Question

Я изучаю Dynami c Программирование на GeeksForGeeks и у меня возникла проблема с проблемой укладки плиток и способом ее решения единицы высоты укладываются вертикально таким образом, чтобы плитка большего размера не размещалась на плитке меньшего размера. Пример показан ниже:

We have infinite number of tiles of sizes 1, 2, …, m. The task is calculate the number of different stable tower of height n that can be built from these tiles, with a restriction that you can use at most k tiles of each size in the tower.

Note: Two tower of height n are different if and only if there exists a height h (1 <= h <= n), such that the towers have tiles of different sizes at height h. For example:</p>

Input : n = 3, m = 3, k = 1.
Output : 1
Possible sequences: { 1, 2, 3}. 
Hence answer is 1.

Input : n = 3, m = 3, k = 2.
Output : 7
{1, 1, 2}, {1, 1, 3}, {1, 2, 2},
{1, 2, 3}, {1, 3, 3}, {2, 2, 3}, 
{2, 3, 3}.

The way to solve is to count number of decreasing sequences of length n using numbers from 1 to m where every number can be used at most k times. We can recursively compute count for n using count for n-1.

Declare a 2D array dp[][], where each state dp[i][j] denotes the number of decreasing sequences of length i using numbers from j to m. We need to take care of the fact that a number can be used a most k times. This can be done by considering 1 to k occurrences of a number. Hence our recurrence relation becomes:

введите описание изображения здесь

Также мы можем использовать тот факт, что для фиксированного j мы используем последовательные значения предыдущих k значений i. Следовательно, мы можем поддерживать массив суммы префиксов для каждого состояния. Теперь мы избавились от коэффициента k для каждого состояния.

Я читал этот алгоритм много раз, но не понимаю его и как доказать его точность. Я пытался найти руководство по inte rnet, но только его вариации. Пожалуйста, помогите мне это объяснить.

Answer 1

Мы можем доказать это, сформировав логическое повторение:

(A) Если максимальная высота стека при заданных m и k меньше n, мы не можем создать никакой стек.

( Б) Если разрешен только один тайл, мы можем выбрать m разных размеров для этого тайла.

(C) Если разрешен только один размер, если k больше или равно n, мы можем построить одна стопка из n плиток размера 1; в противном случае - ноль стеков.

(D) Для каждого возможного количества x плиток размера m, сложенных в стопку, у нас есть один способ, который умножается на количество способов укладки (n - x) плиток, используя размеры не более (m - 1), поскольку мы использовали m.

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

Вот демонстрация повторения в JavaScript (извините, я не разбираюсь в C ++, но первая функция, f, которая вычисляет только количество, должна быть очень легко преобразовать):

// Returns the count
function f(n, m, k){
  if (n > m * k)
    return 0;
  
  if (n == 1)
    return m;
    
  if (m == 1)
    return n <= k ? 1 : 0;
   
  let result = 0;

  for (let x=0; x<=k; x++)
    result += f(n - x, m - 1, k);
    
  return result;
}

// Returns the sequences
function g(n, m, k){
  if (n > m * k)
    return [];
  
  if (n == 1)
    return new Array(m).fill(0).map((_, i) => [i + 1]);
    
  if (m == 1)
    return n <= k ? [new Array(n).fill(1)] : [];
   
  let result = [];

  for (let x=0; x<=k; x++){
    const pfx = new Array(x).fill(m);
    const prev = g(n - x, m - 1, k);

    for (let s of prev)
      result.push(pfx.concat(s));
  }
    
  return result;
}

var inputs = [
  [3, 3, 1],
  [3, 3, 2],
  [1, 2, 2]
];

for (let args of inputs){
  console.log('' + args);
  console.log(f(...args));
  console.log(JSON.stringify(g(...args)));
  console.log('');
}

Answer 2

• Обратите внимание, что плитка самого большого размера (m) может отображаться только внизу.
• Его внешний вид последовательный
• Ваше повторение станет:

T(n,m,k) = SIGMA_{i=0,...,k} T(n-i,m-1,k)

• Затем вам нужно определить базовые случаи повторения:

T(n,m,1) = // can you tell what this is?
T(n,1,k) = // can you tell what this is?
T(1,m,k) = m // this is easy