умножьте числа на всех путях и получите число с минимальным количеством нулей
я имею m*n таблица, в которой каждая запись имеет значение.
стартовая позиция в верхний левый угол, и я могу идти право или же вниз пока я не достигну Нижний правый угол.
Я хочу путь, который, если я умножу числа на этом пути, я получу число, у которого есть минимальное количество нулей в его правой стороне.
пример:
1 2 100
5 5 4
возможные пути:
1*2*100*4=800
1*2*5*4= 40
1*5*5*4= 100
Решение : 1*2*5*4= 40 потому что 40 имеют 1 ноль, а другие пути имеют 2 ноля.
Самый простой способ — использовать DFS и рассчитать все пути. но это не эффективно.
Я ищу оптимальную подструктуру для ее решения с использованием динамического программирования.
Подумав немного, я пришел к следующему уравнению:
T(i,j) = CountZeros(T(i-1,j)*table[i,j]) < CountZeros(T(i,j-1)*table[i,j]) ?
T(i-1,j)*table[i,j] : T(i,j-1)*table[i,j]
Код:
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
using Table = vector<vector<int>>;
const int rows = 2;
const int cols = 3;
Table memo(rows, vector<int>(cols, -1));
int CountZeros(int number)
{
if (number < 0)
return numeric_limits<int>::max();
int res = 0;
while (number != 0)
{
if (number % 10 == 0)
res++;
else break;
number /= 10;
}
return res;
}int solve(int i, int j, const Table& table)
{
if (i < 0 || j < 0)
return -1;
if (memo[i][j] != -1)
return memo[i][j];
int up = solve(i - 1, j, table)*table[i][j];
int left = solve(i, j - 1, table)*table[i][j];
memo[i][j] = CountZeros(up) < CountZeros(left) ? up : left;
return memo[i][j];
}
int main()
{
Table table =
{
{ 1, 2, 100 },
{ 5, 5, 4 }
};
memo[0][0] = table[0][0];
cout << solve(1, 2, table);
}
Но это не оптимально (например, в приведенном выше примере это дает 100)
Любая идея для лучшей оптимальной подструктуры? я могу решить это с помощью динамического программирования ?!
Решение
Давайте пересмотрим уравнение оптимальности Беллмана для вашей задачи. Я рассматриваю это как системный подход к таким проблемам (тогда как я часто не понимаю однострочников DP). Моя ссылка книга Саттона и Барто.
государство в которой ваша система может быть описана тройкой целых чисел (i,j,r) (который моделируется как std::array<int,3>). Вот, i а также j обозначить столбец и строку в вашем прямоугольнике M = m_{i,j}, в то время как r обозначает результат умножения.
Ваш действия в состоянии (i,j,r) даны, идя rightс которым ты заканчиваешь в государстве (i, j+1, r*m_{i,j+1}) или спускаясь, что приводит к состоянию (i+1, j, r*m_{i+1,j}),
Тогда уравнение Беллмана
v(i,j,r) = min{ NullsIn(r*m_{i+1,j}) - NullsIn(r) + v_(i+1,j, r*m_{i+1,j})
NullsIn(r*m_{i,j+1}) - NullsIn(r) + v_(i,j+1, r*m_{i,j+1}) }
Обоснование этого уравнения заключается в следующем: NullsIn(r*m_{i+1,j}) - NullsIn(r) обозначает нули, которые вы должны добавить при выполнении одного из двух действий, то есть мгновенного штрафа. v_(i+1,j, r*m_{i+1,j}) обозначает нули в состоянии, в которое вы попали, когда выполняете это действие. Теперь хочется предпринять действия, которые минимизируют оба вклада.
Что вам нужно дальше, это только функция int NullsIn(int) который возвращает нули в данном целом числе. Вот моя попытка:
int NullsIn(int r)
{
int ret=0;
for(int j=10; j<=r; j*=10)
{
if((r/j) * j == r)
++ret;
}
return ret;
}
Для удобства я дополнительно определил NullsDifference функция:
int NullsDifference(int r, int m)
{
return NullsIn(r*m) - NullsIn(r);
}
Теперь нужно выполнить обратную итерацию, начиная с начального состояния в правом нижнем элементе матрицы.
int backwardIteration(std::array<int,3> state, std::vector<std::vector<int> > const& m)
{
static std::map<std::array<int,3>, int> memoization;
auto it=memoization.find(state);
if(it!=memoization.end())
return it->second;
int i=state[0];
int j=state[1];
int r=state[2];
int ret=0;
if(i>0 && j>0)
{
int inew=i-1;
int jnew=j-1;
ret=std::min(NullsDifference(r, m[inew][j]) + backwardIteration({inew,j,r*m[inew][j]}, m),
NullsDifference(r, m[i][jnew]) + backwardIteration({i,jnew,r*m[i][jnew]}, m));
}
else if(i>0)
{
int inew=i-1;
ret= NullsDifference(r, m[inew][j]) + backwardIteration({inew,j,r*m[inew][j]}, m);
}
else if(j>0)
{
int jnew=j-1;
ret= NullsDifference(r, m[i][jnew]) + backwardIteration({i,jnew,r*m[i][jnew]}, m);
}
memoization[state]=ret;
return ret;
}
Эта процедура называется через
int main()
{
int ncols=2;
int nrows=3;
std::vector<std::vector<int> > m={{1,2,100}, {5,5,4}};
std::array<int,3> initialState = {ncols-1, nrows -1, m[ncols-1][nrows - 1]};
std::cout<<"Minimum number of zeros: "backwardIteration(initialState, m)<<"\n"<<std::endl;
}
Для вашего массива он печатает желаемый 1 для числа нулей.
Вот живое демо на Coliru.
РЕДАКТИРОВАТЬ
Здесь важная вещь: в производстве вы обычно не звоните backwardIteration как я сделал, потому что это требует экспоненциально увеличивающегося количества рекурсивных вызовов. Скорее, вы начинаете в верхнем левом углу и вызываете его, затем сохраняете результат. Далее вы идете влево и вниз и каждый раз звоните backwardIteration где вы теперь используете ранее сохраненный результат. И так далее.
Чтобы сделать это, нужна концепция запоминания в функции backwardIteration, который возвращает уже сохраненный результат вместо вызова другого рекурсивного вызова.
Я добавил памятку в вызове функции выше. Теперь вы можете циклически перемещаться по массиву с левого верхнего до правого нижнего угла любым удобным вам способом, но предпочтительно делать небольшие шаги, такие как строка за строкой, столбец за столбцом или прямоугольник за прямоугольником.
На самом деле, это и только это дух динамического программирования.
Другие решения