Şən funksiya (Həll təhlili)

Rekursiv funksiya və memoizasiya ilə implementasiya edəcəyik.

Alqoritm İmplementasiyası

Funksiyanın dəyərlərini memoizasiya etmək üçün iki ölçülü massiv elan edin: dp[x][y] = f(x, y).

long long dp[51][51];

Memoizasiya ilə rekursiv funksiyanın implementasiyası.

long long f(int x, int y)
{
    if (x <= 0 || y <= 0) return 0;
    if (dp[x][y] != -1) return dp[x][y];
    if (x <= y) return dp[x][y] = f(x-1,y-2) + f(x-2,y-1) + 2;
    return dp[x][y] = f(x-2,y-2) + 1;
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyun. dp massivinin hüceyrələrini -1 dəyəri ilə başlatın. f(x, y) funksiyasını çağırın və onun dəyərini çap edin.

scanf("%d %d",&x,&y);
memset(dp,-1,sizeof(dp));
printf("%lld\n",f(x,y));