Еще я бы добавил ссылку к первоисточнику. Данный алгоритм был придуман Робертом Флойдом в 1964 году, как часть алгоритма TreeSort: Floyd, Robert W., (1964), Algorithm 245 — Treesort 3, Communications of the ACM 7 (12): 701
// Problem 1 (Naive)
// O(k^k)
public static int smsNaive(int k) {
int result = 0;
for (int i = 1; i < k + 1; i++) {
result += smsNaiveHelper(i);
}
return result;
}
public static int smsNaiveHelper(int k) {
if (k < 0) return 0;
if (k == 0) return 1;
return 8 * smsNaiveHelper(k - 1) +
8 * smsNaiveHelper(k - 2) +
8 * smsNaiveHelper(k - 3) +
2 * smsNaiveHelper(k - 4);
}
// Problem 1 (DP)
// O(k^2)
public static int smsDP(int k) {
// dp[i] - is a number of messages
// that uses 'i' presses
int dp[] = new int[k + 1];
// initial state
// we can write only one message (an empty with length 0) by zero presses
dp[0] = 1;
// result
int result = 0;
// fill the dp
for (int i = 1; i < k + 1; i++) {
dp[i] += dp[i - 1] * 8;
if (i - 1 > 0) {
dp[i] += dp[i - 2] * 8;
}
if (i - 2 > 0) {
dp[i] += dp[i - 3] * 8;
}
if (i - 3 > 0) {
dp[i] += dp[i - 4] * 2;
}
result += dp[i];
}
return result;
}
Небольшая поправочка к первому примеру. Ответ будет не сумма *всех* состояний а сумма состояний при (j == k) т.е. сумма последнего столбца в матрице dp. По условию dp[i][j] содержит количество сообщений длины i, которые можно напечатать используя не больше j нажатий. Т.е. нас интересует только последний столбец, т.к. он и содержит ответы.
Как то сумбурно написал, но надеюсь понятно.
Вот код
// Problem 1 (DP)
// O(k^2)
public static int smsDP(int k) {
// base case
if (k == 0) return 1;
// dp[i][j] - is a number of messages
// that with length 'i' that uses 'j' presses
int dp[][] = new int[k + 1][k + 1];
// initial state
// we can write only one message (an empty with length 0) by zero presses
//for (int i = 0; i < k; i++) {
dp[0][0] = 1;
//}
// answer
int result = 0;
// fill the dp
// we can't write message with length M by pressing N keys, where M > N
// this is why we're trying to get an upper triangular matrix
for (int i = 1; i < k + 1; i++) {
for (int j = i; j < k + 1; j++) {
dp[i][j] = dp[i - 1][j - 1] * 8;
if (j - 1 > 0) {
dp[i][j] += dp[i - 1][j - 2] * 8;
}
if (j - 2 > 0) {
dp[i][j] += dp[i - 1][j - 3] * 8;
}
if (j - 3 > 0) {
dp[i][j] += dp[i - 1][j - 4] * 2;
}
if (j == k) {
result += dp[i][j];
}
}
}
return result;
}
Имел ввиду, что в Кормене есть отличный пример «трудностей перевода» — «пирамидальная сортировка» она же «heap sort». Лучше не переводить такие вещи. ИМХО.
А я вот не понимаю зачем переводить название алгоритмов и структур. Я не стараюсь сколько-нибудь приубавить ценности стати, но честно не понимаю мотивацию. Меня все эти «сортировка слиянием» (а в Кормене «пирамидальная сортировка») только путают. Давно просто merge не перевожу как «слияние» перевожу как «мержить», поэтому долго сначала не мог понять, что за сортировка такая о которой я ничего не слышал :)
1. Открыть мотомастерскую и периодически строить мотоциклы по индивидуальному заказу — мечта прям.
2. Фитнес-тренер — тут надо немного улучшить форму и почитать литературы + пройти курсы
3. В университете/школе бы математику преподавал.
«браузер с социальными сетями» — да ну. Тут фантазия у таких трудоголиков не скупится на черные консоли и разноцветные портянки бесконечного кода. Это уж вы зря. Пустить пыль в глаза мы они всегда умеют.
Если первую двадцатку смотреть — восемь мест российских. Приятно, хоть сам не большой болельщик и фанат. Гордость берет еще за родной политех (АлтГТУ), который обскакал всякие МИТы и Стенфорды и чутка не дотянул до бронзовой медали (15-ое место). Так держать! Все молодцы!
Кто-то недавно говорил (переведено на русский): «Чтение документации это как поиск в связном списке. Использование SO это как запрос к хеш-таблице.» Ну т.е. O(n) против О(1).
Как то сумбурно написал, но надеюсь понятно.
Извиняюсь за твердолобость, но можно ссылку на почитать про товарища А. Кумок. Уж больно цитата в начале статьи понравилась.
Отличная статья. Спасибо.
1. Открыть мотомастерскую и периодически строить мотоциклы по индивидуальному заказу — мечта прям.
2. Фитнес-тренер — тут надо немного улучшить форму и почитать литературы + пройти курсы
3. В университете/школе бы математику преподавал.
мыони всегда умеют.