czwartek, grudnia 02, 2021

Czy to jeszcze dynamic programming? ;-)

Takie coś przed chwilą popełniłem w ramach ćwiczenia dynamic programming ;-)

public static final int TYPE = 0;
public static final int PASTE = 1;
public static final int COPY = 2;
public static final int SELECT = 3;
Function<Integer,Integer> ADD_1 = k -> k+1;
Function<Integer,Integer> ADD_0 = k -> k+0;
Function<Integer,Integer> MUL_2 = k -> k*2;

private Function<Integer,Integer> max(Function<Integer,Integer> a, Function<Integer, Integer> b) {
if (a.apply(Integer.valueOf(2))>b.apply(Integer.valueOf(2))) return a;
return b;
}

public int howMany(int keystrokes) {
var dp = new Function[keystrokes][4];
dp[keystrokes-1][TYPE]=ADD_1;
dp[keystrokes-1][PASTE]=MUL_2;
dp[keystrokes-1][COPY]=ADD_0;
dp[keystrokes-1][SELECT]=ADD_0;
for (var i=keystrokes-2; i>=0; i--) {
dp[i][TYPE]=max(dp[i+1][TYPE].compose(ADD_1),dp[i+1][SELECT].compose(ADD_1));
dp[i][PASTE]=max(dp[i+1][TYPE].compose(ADD_1),dp[i+1][SELECT]);
dp[i][COPY]=dp[i+1][PASTE];
dp[i][SELECT]=dp[i+1][COPY];

}
return (Integer)dp[0][0].apply(Integer.valueOf(1))-1;
}

I nie wiem czy się jeszcze to liczy jako Dynamic Programming, czy już nie ;-)

Tu to samo jako obrazek ;-)

Ogólna idea jest taka, że składamy funkcje z innych funkcji i w razie czego liczymy "max" funkcji ;-)

Spełnia wg mnie wymagania dynamic programming, ale jest dziwne ;-)

Jakby co ma błąd, ale na razie mi bardziej zależało na sprawdzeniu koncepcji niż znalezieniu rozwiązania ;p




Podobne postybeta
Struktury danych vs algorytmy
Ile to jest 1+1 w Java'ie?
Java i liczby pierwsze, odsłona druga
Człowiek się uczy całe życie - źle rozumiałem cache'owanie Integerów :-)
Zdradliwa Java i 8 królowych ;-)

Brak komentarzy:

Prześlij komentarz