pd.md

Programação dinâmica 2

Guardar informações na memória para não ter que fazer uma computação muitas vezes.

int fib(int i) {
    if (i == 1 || i == 0) return 1;
    return fib(i-1) + fib(i-1);
}

O código acima é ruim pois faz a mesma conta muitas vezes.

Receitinha para PD:

• Declarar a memória
• Definir condição de parada
• Estados
  • Não podem ciclar (se não entra em loop infinito)
  • Caber na memória
  • Resposta única (independente de como você chegou a determinado estado)
  • Guardar a resposta e retornar

Últimos dígitos da sequência de Fibonacci:

long long memo[1000001];
long long fib(int i) {
    if (i == 1 || i == 2) return 1;
    if (memo[i] == -1) {
        memo[i] = fib(i-1) + fib(i-2) % MOD;
    }
    return memo[i];
}

Problema do troco sem repetir moedas:

int moedas[1001];
int memo[1001]
bool dp (int din, int i) {
    if (din == 0) return 1;
    if (din < 0 || i == n) return 0;
    if (memo[din][i] == 1) {
    	memo[din][i] = dp(din - moedas[i], i+1) || dp(din, i + 1);
    }
    return memo[din][i];
}

LCS (longest common sequence)

int n, m;
string s1, s2;
int memo[1001][1001];
int lcs(int i, int j) {
    if (i == n || j == m) return 0;
    if (memo[i][j] == -1) {
        if (s1[i] == s2[j])
            memo[i][j] = 1 + lcs(i + 1, j + 1);
	    else
        	memo[i][j] = max(lcs(i+j, j), lcs(i, j + 1));
    }
    return memo[i][j];
}

LIS (longest increasing sequence)

10^3 números, vão de 0 a 10^9

int n;
int v[1123];
int memo[1123][1123];

int lis(int i, int last) {
    if (i == n) return 0;
    if (memo[i][last] == -1) {
        memo[i][last] == lis(i+1, last);
        if (v[i] > v[last])
            memo[i][last] = max(memo[i][last], 1+lis(i+1, i))
    }
    return memo[i][j];
}

Problema da mochila

int w[1123];
int v[1123];
int memo[1123][1123];

int pd(int i, int mo) {
    // mo: quanto mochila ainda aguenta
    if (mo < 0) return -INF;
    if (i == n) return 0;

    if (memo[i][mo] == -1) {
        memo[i][mo] = max(v[i] + pd(i+1, mo - w[i]), pd(i+1, mo));
    }
    return memo[i][mo];
}

outro problema

int v[1123];
int memo[2][1123][1123];
int pd(int j, int c, int f) {
    if (f < c)
    	return 0;
    if (memo[j][c][f] == INF) {
        if (j == 0)
            memo[j][c][f] == max(v[c] + pd(1, c+1, f), v[f] + pd(1, c, f-1));
        else
            memo[j][c][f] = min(pd(0, c+1, f), pd(0, c, f-1));
    }
    return memo[j][c][f];
}