История изменений
Исправление fsb4000, (текущая версия) :
В элементе матрицы dp[i][j] содержится количество плюсов необходимое для получения числа i в подстроке длины j.
Сначала все элементы матрицы 10000(можно любое положительное число которое заведомо больше ответа, только INT_MAX не нужно выбирать чтобы не было переполнения) и dp[0][0]=-1
Потом обходим все подстроки и заполняем матрицу.
Вот отрывок:
// ...
for (j = i - 1; j >= i - 4 && j >= 0; j--) {
x = parse_substring(full_string, len - i, len - j);
for (k = 0; k + x <= n; k++) {
if (dp[k + x][i] > dp[k][j] + 1)
{
dp[k + x][i] = dp[k][j] + 1;
}
// ....
}
}
Вот ещё добавил принты в функцию как выводит: https://pastebin.com/yc31yZwL
Но это не всё, дальше ещё нужно будет решить вопрос с нулями…
Если решишь, кинь потом в тему своё решение на хаскеле…
Исправление fsb4000, :
В элементе матрицы dp[i][j] содержится количество плюсов необходимое для получения числа i в подстроке длины j.
Сначала все элементы матрицы 10000(можно любое положительное число которое заведомо больше ответа, только INT_MAX не нужно выбирать чтобы не было переполнения) и dp[0][0]=-1
Потом обходим все подстроки и заполняем матрицу.
Вот отрывок:
// ...
for (j = i - 1; j >= i - 4 && j >= 0; j--) {
x = parse_substring(full_string, len - i, len - j);
for (k = 0; k + x <= n; k++) {
if (dp[k + x][i] > dp[k][j] + 1)
{
dp[k + x][i] = dp[k][j] + 1;
}
// ....
}
}
Вот ещё добавил принты в функцию как выводит: https://pastebin.com/yc31yZwL
Но это не всё, дальше ещё нужно будет решить вопрос с нулями…
Исходная версия fsb4000, :
В элементе матрицы dp[i][j] содержится количество плюсов необходимое для получения числа i в подстроке длины j.
Сначала все элементы матрицы 10000(можно любое положительное число которое заведомо больше ответа, только INT_MAX не нужно выбирать чтобы не было переполнения) и dp[0][0]=-1
Потом обходим все подстроки и заполняем матрицу.
Вот отрывок:
x = parse_substring(full_string, len - i, len - j);
for (k = 0; k + x <= n; k++) {
if (dp[k + x][i] > dp[k][j] + 1)
{
dp[k + x][i] = dp[k][j] + 1;
}
// ....
}
Вот ещё добавил принты в функцию как выводит: https://pastebin.com/yc31yZwL
Но это не всё, дальше ещё нужно будет решить вопрос с нулями…