Resolvendo o Problema do Triângulo Numérico com Programação Dinâmica
O problema do Triângulo Numérico é um exercício fundamental em Programação Dinâmica (PD). Consiste em uma estrutura triangular de números, onde o objetivo é determinar o caminho de cima para baixo que resulta na maior soma, movendo-se apenas para as células adjacentes na linha inferior (direta ou esquerda).
Definição do Estado de PD
Para abordar este problema com Programação Dinâmica, definimos um estado dp[linha][coluna]. Este estado representa a soma máxima de todos os caminhos que iniciam no vértice superior do triângulo e terminam na célula (linha, coluna). A "propriedade" que cada estado armazena é, portanto, o valor máximo acumulado até aquele ponto.
Equação de Recorrência (Abordagem Top-Down)
Para alcançar uma célula (linha, coluna), um caminho deve ter vindo de uma das duas células na linha imediatamente superior: (linha-1, coluna-1) (diagonal superior esquerda) ou (linha-1, coluna) (diagonal superior direita). Assim, o valor de dp[linha][coluna] é o número na célula (linha, coluna) somado ao máximo dos valores dp das duas células anteriores.
A equação de recorrência é:
dp[linha][coluna] = max(dp[linha-1][coluna-1], dp[linha-1][coluna]) + valores_triangulo[linha][coluna];
Inicialização e Casos de Fronteira
A inicialização da tabela dp requer atenção. Como os números no triângulo podem ser negativos e buscamos uma soma máxima, é prudente inicializar a matriz dp com um valor de "infinito negativo" (-INF). Isso assegura que qualquer caminho válido, mesmo que resulte em uma soma negativa, será maior que -INF e considerado nas comparações.
Para as células nas bordas (as primeiras e últimas colunas de cada linha, exceto o vértice), um dos antecessores diagonais pode não existir. Nesses casos, o valor -INF da célula inválida garantirá que a função max naturalmente descarte essa direção, escolhendo o caminho válido.
O caso base é o vértice do triângulo: dp[1][1] = valores_triangulo[1][1].
#include <iostream>
#include <vector>
#include <algorithm> // Para std::max
#include <cstring> // Para memset
const int DIMENSAO_MAX = 510;
const int INF_NEG = 0x3f3f3f3f; // Representa um valor muito grande, usado como -INF para maximização
int dp_soma_maxima[DIMENSAO_MAX][DIMENSAO_MAX];
int numeros_triangulo[DIMENSAO_MAX][DIMENSAO_MAX];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_linhas;
std::cin >> num_linhas;
for (int i = 1; i <= num_linhas; ++i) {
for (int j = 1; j <= i; ++j) {
std::cin >> numeros_triangulo[i][j];
}
}
// Inicializa a tabela dp com infinito negativo
// memset é usado com -INF. Para 0x3f3f3f3f, isso é equivalente a um valor negativo quando interpretado como int
// No entanto, para segurança, é melhor fazer o loop e atribuir -INF
for (int i = 0; i <= num_linhas; ++i) {
for (int j = 0; j <= num_linhas; ++j) {
dp_soma_maxima[i][j] = -INF_NEG; // Explicitamente -INF
}
}
// Caso base: o valor no vértice do triângulo
dp_soma_maxima[1][1] = numeros_triangulo[1][1];
// Itera pelas linhas do triângulo, a partir da segunda
for (int i = 2; i <= num_linhas; ++i) {
for (int j = 1; j <= i; ++j) {
int valor_origem_esquerda = dp_soma_maxima[i-1][j-1];
int valor_origem_direita = dp_soma_maxima[i-1][j];
// As bordas do triângulo têm apenas uma origem válida
if (j == 1) { // Primeira coluna: só pode vir de (i-1, j)
dp_soma_maxima[i][j] = valor_origem_direita + numeros_triangulo[i][j];
} else if (j == i) { // Última coluna: só pode vir de (i-1, j-1)
dp_soma_maxima[i][j] = valor_origem_esquerda + numeros_triangulo[i][j];
} else { // Células internas: podem vir de ambas as direções
dp_soma_maxima[i][j] = std::max(valor_origem_esquerda, valor_origem_direita) + numeros_triangulo[i][j];
}
}
}
// O resultado final é o maior valor na última linha do triângulo
int soma_total_maxima = -INF_NEG;
for (int j = 1; j <= num_linhas; ++j) {
soma_total_maxima = std::max(soma_total_maxima, dp_soma_maxima[num_linhas][j]);
}
std::cout << soma_total_maxima << std::endl;
return 0;
}
Abordagem Bottom-Up
Uma estratégia alternativa, frequentemente mais simples em termos de tratamento de fronteiras, é a abordagem bottom-up. Começamos da base do triângulo e subimos até o vértice.
Nesta abordagem, dp[linha][coluna] representa a soma máxima de um caminho que começa na célula (linha, coluna) e desce até a base do triângulo. Para calcular dp[linha][coluna], consideramos as duas células na linha inferior às quais é possível se mover: (linha+1, coluna) (diretamente abaixo) e (linha+1, coluna+1) (diagonal abaixo-direita).
A equação de recorrência é:
dp[linha][coluna] = max(dp[linha+1][coluna], dp[linha+1][coluna+1]) + valores_triangulo[linha][coluna];
A linha de base para esta abordagem é a última linha do triângulo. As células dp[num_linhas][j] são inicializadas diretamente com os valores_triangulo[num_linhas][j]. A partir daí, podemos preencher a tabela para cima, sem a necessidade de valores -INF, pois todas as transições para baixo são válidas a partir de qualquer ponto intermediário.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::max
const int DIMENSAO_MAX_BU = 510;
int dp_soma_maxima_bu[DIMENSAO_MAX_BU][DIMENSAO_MAX_BU];
int numeros_triangulo_bu[DIMENSAO_MAX_BU][DIMENSAO_MAX_BU];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_linhas;
std::cin >> num_linhas;
for (int i = 1; i <= num_linhas; ++i) {
for (int j = 1; j <= i; ++j) {
std::cin >> numeros_triangulo_bu[i][j];
}
}
// Inicializa a última linha da tabela dp diretamente com os valores do triângulo
for (int j = 1; j <= num_linhas; ++j) {
dp_soma_maxima_bu[num_linhas][j] = numeros_triangulo_bu[num_linhas][j];
}
// Preenche a tabela dp de baixo para cima, linha por linha
for (int i = num_linhas - 1; i >= 1; --i) {
for (int j = 1; j <= i; ++j) {
dp_soma_maxima_bu[i][j] = std::max(dp_soma_maxima_bu[i+1][j], dp_soma_maxima_bu[i+1][j+1]) + numeros_triangulo_bu[i][j];
}
}
// O resultado final será o valor do vértice do triângulo (1,1)
std::cout << dp_soma_maxima_bu[1][1] << std::endl;
return 0;
}
Problemas Relacionados: Otimização de Caminhos em Grades
- Coleta de Amendoins (Máximo em Grade)
Este problema é uma aplicação direta da mesma lógica do Triângulo Numérico, mas em uma grade retangular. O objetivo é coletar o máximo de itens (por exemplo, amendoins) ao mover-se de (1,1) para (N,M), permitido apenas movimentos para baixo ou para a direita.
O estado dp[i][j] representa o total máximo de amendoins coletados ao alcançar a célula (i,j). Para chegar a (i,j), só é possível vir de (i-1,j) (de cima) ou (i,j-1) (da esquerda).
Equação de recorrência:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + valores_grade[i][j];
As células da primeira linha e primeira coluna (dp[0][j] e dp[i][0]) são implicitamente 0, representando que não há valor acumulado antes de entrar na grade.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::max
#include <cstring> // Para memset
const int MAX_DIM_GRID = 110;
int grade_amendoins[MAX_DIM_GRID][MAX_DIM_GRID];
int dp_max_coletado[MAX_DIM_GRID][MAX_DIM_GRID];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_casos_teste;
std::cin >> num_casos_teste;
while (num_casos_teste--) {
int linhas, colunas;
std::cin >> linhas >> colunas;
// Zera a tabela DP para cada caso de teste
memset(dp_max_coletado, 0, sizeof(dp_max_coletado));
for (int i = 1; i <= linhas; ++i) {
for (int j = 1; j <= colunas; ++j) {
std::cin >> grade_amendoins[i][j];
}
}
// A primeira linha e coluna da tabela DP (índice 0) já são 0 por memset,
// o que funciona como base para os cálculos.
for (int i = 1; i <= linhas; ++i) {
for (int j = 1; j <= colunas; ++j) {
dp_max_coletado[i][j] = std::max(dp_max_coletado[i-1][j], dp_max_coletado[i][j-1]) + grade_amendoins[i][j];
}
}
std::cout << dp_max_coletado[linhas][colunas] << std::endl;
}
return 0;
}
Variação: Valor Máximo de Joias (Indexação em 0)
Um porblema comum que segue o mesmo padrão é o de encontrar o "Valor Máximo de Joias" em uma grade. A principal diferença é que as grades podem usar indexação baseada em 0 (de [0][0] a [N-1][M-1]). Pode ser resolvido por memoização (recursão com cache) ou PD iterativa.
Abordagem 1: Memoização Recursiva
Utiliza uma função recursiva para calcular o valor máximo, armazenando os resultados em uma tabela de memorização para evitar recomputações.
#include <vector>
#include <algorithm> // Para std::max
#include <cstring> // Para memset
// Exemplo para um ambiente de classes (e.g., LeetCode)
class Solution {
private:
int memo_joias[210][210]; // Tabela de memorização, tamanho ajustável
std::vector<std::vector<int>>* grade_joias_ptr; // Ponteiro para a grade original
int calcular_valor_max_recursivo(int r, int c) {
// Casos base: fora dos limites da grade, o valor é 0
if (r < 0 || c < 0) {
return 0;
}
// Se o valor já foi calculado e armazenado, retorna-o
if (memo_joias[r][c] != -1) { // -1 indica que não foi calculado
return memo_joias[r][c];
}
// Recorrência: soma o valor atual com o máximo das origens válidas
int valor_celula_atual = (*grade_joias_ptr)[r][c];
int max_de_cima = calcular_valor_max_recursivo(r - 1, c);
int max_da_esquerda = calcular_valor_max_recursivo(r, c - 1);
return memo_joias[r][c] = std::max(max_de_cima, max_da_esquerda) + valor_celula_atual;
}
public:
int jewelleryValue(std::vector<std::vector<int>>& grade_joias) {
int num_linhas = grade_joias.size();
int num_colunas = grade_joias[0].size();
grade_joias_ptr = &grade_joias;
// Inicializa a tabela de memorização com -1 para marcar estados não calculados
// (Supondo que os valores das joias são não-negativos)
memset(memo_joias, -1, sizeof(memo_joias));
return calcular_valor_max_recursivo(num_linhas - 1, num_colunas - 1);
}
};
Abordagem 2: PD Iterativa com Ajuste de Índice
Para evitar lidar com índices negativos em grades 0-indexadas, uma técnica comum é deslocar os índices da tabela DP em 1. Assim, dp_tabela[i+1][j+1] corresponde à célula (i,j) da grade original. As linhas/colunas 0 da dp_tabela servem como "fronteiras virtuais" com valor 0.
#include <vector>
#include <algorithm> // Para std::max
#include <cstring> // Para memset
class Solution {
public:
int jewelleryValue(std::vector<std::vector<int>>& grade_joias) {
const int MAX_DIM_DP = 210;
int dp_tabela_iterativa[MAX_DIM_DP][MAX_DIM_DP];
memset(dp_tabela_iterativa, 0, sizeof(dp_tabela_iterativa)); // Inicializa com 0 (valores não-negativos)
int num_linhas = grade_joias.size();
int num_colunas = grade_joias[0].size();
for (int r = 0; r < num_linhas; ++r) {
for (int c = 0; c < num_colunas; ++c) {
// dp_tabela_iterativa[r+1][c+1] armazena o resultado para grade_joias[r][c]
dp_tabela_iterativa[r + 1][c + 1] = std::max(dp_tabela_iterativa[r + 1][c], dp_tabela_iterativa[r][c + 1]) + grade_joias[r][c];
}
}
return dp_tabela_iterativa[num_linhas][num_colunas];
}
};
- Custo Mínimo de Passagem
Neste problema, o objetivo é encontrar o caminho de (1,1) para (N,N) em uma grade, minimizando o custo total, novamente com movimentos restritos a baixo e direita.
O estado dp[i][j] representa o custo mínimo para alcançar a célula (i,j). A equação de recorrência é:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + custo_grade[i][j];
Para problemas de minimização, a tabela dp (excluindo o ponto de partida) deve ser inicializada com um "infinito positivo" (+INF). Isso garante que qualquer caminho real terá um custo menor e será selecionado. O custo da célula inicial dp[1][1] é simplesmente custo_grade[1][1].
As células da primeira linha e primeira coluna são casos especiais, pois só podem ser alcançadas de uma direção. Portanto, devem ser preenchidas sequencialmente.
#include <iostream>
#include <algorithm> // Para std::min
#include <cstring> // Para memset
const int MAX_DIM_CUSTO = 110;
const int INF_POS = 0x3f3f3f3f; // Representa um valor muito grande, usado como +INF
int grade_custos[MAX_DIM_CUSTO][MAX_DIM_CUSTO];
int dp_custo_minimo[MAX_DIM_CUSTO][MAX_DIM_CUSTO];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int tamanho_grade;
std::cin >> tamanho_grade;
for (int i = 1; i <= tamanho_grade; ++i) {
for (int j = 1; j <= tamanho_grade; ++j) {
std::cin >> grade_custos[i][j];
}
}
// Inicializa toda a tabela dp_custo_minimo com INF_POS
memset(dp_custo_minimo, INF_POS, sizeof(dp_custo_minimo));
// O custo para a célula inicial (1,1) é o valor da própria célula
dp_custo_minimo[1][1] = grade_custos[1][1];
// Preencher a primeira linha (movendo apenas para a direita)
for (int j = 2; j <= tamanho_grade; ++j) {
dp_custo_minimo[1][j] = dp_custo_minimo[1][j-1] + grade_custos[1][j];
}
// Preencher a primeira coluna (movendo apenas para baixo)
for (int i = 2; i <= tamanho_grade; ++i) {
dp_custo_minimo[i][1] = dp_custo_minimo[i-1][1] + grade_custos[i][1];
}
// Preencher o restante da grade
for (int i = 2; i <= tamanho_grade; ++i) {
for (int j = 2; j <= tamanho_grade; ++j) {
dp_custo_minimo[i][j] = std::min(dp_custo_minimo[i-1][j], dp_custo_minimo[i][j-1]) + grade_custos[i][j];
}
}
std::cout << dp_custo_minimo[tamanho_grade][tamanho_grade] << std::endl;
return 0;
}
- Obtenção de Valores em Grade com Duas Rotas
Este problema envolve duas entidades (ou duas rotas) se movendo simultaneamente de (1,1) para (N,N) em uma grade. O objetivo é maximizar a soma total dos valores coletados por ambas as rotas. A regra crucial é que se ambas as rotas passarem pela mesma célula, o valor dessa célula é contado apenas uma vez.
Por que a Abordagem Gulosa Falha?
Uma tentação é resolver este problema em duas fases: primeiro, encontrar o caminho de maior valor para a Rota 1, marcar as células visitadas como 0, e depois encontrar o caminho de maior valor para a Rota 2. Essa abordagem é gulosa e quase sempre falha. A escolha localmente ótima da Rota 1 pode inviabilizar um caminho globalmente mais valioso para a Rota 2, levando a uma solução subótima.
Modelagem com DP de Três Dimensões
Para garantir a otimalidade, ambas as rotas devem ser consideradas simultaneamente. Podemos definir um estado dp[r1][c1][r2][c2], representando a soma máxima coletada quando a Rota 1 está em (r1,c1) e a Rota 2 está em (r2,c2).
Uma otimização é possível: como ambas as rotas avançam em "passos" de igual duração (cada movimento para baixo ou direita incrementa a soma das coordenadas em 1), podemos inferir que r1 + c1 = r2 + c2. Seja k = r1 + c1 (o número total de passos desde (1,1)). Então c1 = k - r1 e c2 = k - r2. Isso reduz o espaço de estados para dp[k][r1][r2].
Transições de Estado
Para alcançar os estados (r1, c1) e (r2, c2) no passo k, as duas rotas poderiam ter vindo de quatro combinações de estados no passo k-1:
- Rota 1 veio de cima (
r1-1, c1), Rota 2 veio de cima (r2-1, c2):dp[k-1][r1-1][r2-1] - Rota 1 veio de cima (
r1-1, c1), Rota 2 veio da esquerda (r2, c2-1):dp[k-1][r1-1][r2] - Rota 1 veio da esquerda (
r1, c1-1), Rota 2 veio de cima (r2-1, c2):dp[k-1][r1][r2-1] - Rota 1 veio da esquerda (
r1, c1-1), Rota 2 veio da esquerda (r2, c2-1):dp[k-1][r1][r2]
O valor dp[k][r1][r2] é o máximo entre essas quatro possibilidades, somado aos valores das células grade_valores[r1][c1] e grade_valores[r2][c2]. Se (r1,c1) e (r2,c2) são a mesma célula, seu valor deve ser adicionado apenas uma vez.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::max
#include <cstring> // Para memset
const int MAX_DIM_DUPLA = 15; // Dimensão máxima da grade
// k vai até 2*MAX_DIM_DUPLA, r1 e r2 até MAX_DIM_DUPLA
int grade_valores_dupla[MAX_DIM_DUPLA][MAX_DIM_DUPLA];
int dp_duas_rotas[MAX_DIM_DUPLA * 2][MAX_DIM_DUPLA][MAX_DIM_DUPLA]; // dp[k][r1][r2]
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int dimensao_n;
std::cin >> dimensao_n;
int r_in, c_in, val_in;
// Leitura dos valores da grade até encontrar 0 0 0
while (std::cin >> r_in >> c_in >> val_in && (r_in != 0 || c_in != 0 || val_in != 0)) {
grade_valores_dupla[r_in][c_in] = val_in;
}
// Inicializa a tabela DP com 0 (assumindo valores da grade não-negativos)
memset(dp_duas_rotas, 0, sizeof(dp_duas_rotas));
// k representa a soma das coordenadas (linha + coluna), variando de 2 (para (1,1))
// até 2 * dimensao_n (para (dimensao_n, dimensao_n))
for (int k = 2; k <= 2 * dimensao_n; ++k) {
for (int r1 = 1; r1 <= dimensao_n; ++r1) { // Linha da Rota 1
int c1 = k - r1; // Coluna da Rota 1
// Verifica se a coordenada c1 é válida
if (c1 < 1 || c1 > dimensao_n) {
continue;
}
for (int r2 = 1; r2 <= dimensao_n; ++r2) { // Linha da Rota 2
int c2 = k - r2; // Coluna da Rota 2
// Verifica se a coordenada c2 é válida
if (c2 < 1 || c2 > dimensao_n) {
continue;
}
// Calcula o valor a ser adicionado no passo atual
// Se as rotas estão na mesma célula, o valor é contado apenas uma vez
int valor_celulas_atuais = grade_valores_dupla[r1][c1];
if (r1 != r2 || c1 != c2) {
valor_celulas_atuais += grade_valores_dupla[r2][c2];
}
int& estado_dp_atual = dp_duas_rotas[k][r1][r2];
// Transições das 4 possíveis origens no passo k-1
// As condições de fronteira (e.g., r1-1 < 1) são implicitamente tratadas se dp está inicializado com 0.
// O max(estado_dp_atual, ...) só considerará um caminho válido se ele resultar em um valor positivo
// (assumindo que grade_valores_dupla sempre adiciona um valor >= 0).
// 1. Ambas as rotas vieram de cima
estado_dp_atual = std::max(estado_dp_atual, dp_duas_rotas[k - 1][r1 - 1][r2 - 1] + valor_celulas_atuais);
// 2. Rota 1 de cima, Rota 2 da esquerda
estado_dp_atual = std::max(estado_dp_atual, dp_duas_rotas[k - 1][r1 - 1][r2] + valor_celulas_atuais);
// 3. Rota 1 da esquerda, Rota 2 de cima
estado_dp_atual = std::max(estado_dp_atual, dp_duas_rotas[k - 1][r1][r2 - 1] + valor_celulas_atuais);
// 4. Ambas as rotas vieram da esquerda
estado_dp_atual = std::max(estado_dp_atual, dp_duas_rotas[k - 1][r1][r2] + valor_celulas_atuais);
// Caso base específico para (1,1) para evitar dependência de 0-indices em k-1
if (k == 2 && r1 == 1 && r2 == 1) {
estado_dp_atual = grade_valores_dupla[1][1];
}
}
}
}
std::cout << dp_duas_rotas[dimensao_n * 2][dimensao_n][dimensao_n] << std::endl;
return 0;
}
Passagem de Notas (com Restrição de Não Compartilhar Células)
O problema da "Passagem de Notas", onde duas pessoas trocam notas em uma grade sem poder visitar a mesma célula, é uma aplicação direta do problema de "Obtenção de Valores em Grade com Duas Rotas", desde que todos os valores na grade sejam não-negativos.
A prova é que, se existe um caminho ótimo que se cruza, sempre é possível encontrar um caminho alternativo com a mesma ou maior soma total, sem cruzar na mesma célula (assumindo valores não-negativos). Isso ocorre porque "contornar" uma célula já visitada não diminuiria o valor total coletado. Assim, para maximizar a soma, a restrição "não pode visitar a mesma célula" é trivial, e a solução é idêntica à do problema anterior.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::max
#include <cstring> // Para memset
const int MAX_DIM_NOTAS = 55; // Dimensões máximas da grade (M, N)
// k vai até M+N, r1 e r2 até M
int pontuacoes_grade_notas[MAX_DIM_NOTAS][MAX_DIM_NOTAS];
int dp_passagem_notas[MAX_DIM_NOTAS * 2][MAX_DIM_NOTAS][MAX_DIM_NOTAS];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_linhas, num_colunas;
std::cin >> num_linhas >> num_colunas;
for (int i = 1; i <= num_linhas; ++i) {
for (int j = 1; j <= num_colunas; ++j) {
std::cin >> pontuacoes_grade_notas[i][j];
}
}
// Inicializa dp com 0 (pontuações da grade são não-negativas)
memset(dp_passagem_notas, 0, sizeof(dp_passagem_notas));
// k é a soma das coordenadas (linha + coluna), variando de 2 até num_linhas + num_colunas
for (int k = 2; k <= num_linhas + num_colunas; ++k) {
for (int r1 = 1; r1 <= num_linhas; ++r1) {
int c1 = k - r1;
if (c1 < 1 || c1 > num_colunas) continue;
for (int r2 = 1; r2 <= num_linhas; ++r2) {
int c2 = k - r2;
if (c2 < 1 || c2 > num_colunas) continue;
int pontuacao_atual = pontuacoes_grade_notas[r1][c1];
if (r1 != r2 || c1 != c2) { // Se as rotas não se cruzam, adicione a pontuação da segunda célula
pontuacao_atual += pontuacoes_grade_notas[r2][c2];
}
int& estado_dp_atual = dp_passagem_notas[k][r1][r2];
// Transições das 4 possíveis origens no passo k-1
// 1. Ambas as rotas vieram de cima
estado_dp_atual = std::max(estado_dp_atual, dp_passagem_notas[k - 1][r1 - 1][r2 - 1] + pontuacao_atual);
// 2. Rota 1 de cima, Rota 2 da esquerda
estado_dp_atual = std::max(estado_dp_atual, dp_passagem_notas[k - 1][r1 - 1][r2] + pontuacao_atual);
// 3. Rota 1 da esquerda, Rota 2 de cima
estado_dp_atual = std::max(estado_dp_atual, dp_passagem_notas[k - 1][r1][r2 - 1] + pontuacao_atual);
// 4. Ambas as rotas vieram da esquerda
estado_dp_atual = std::max(estado_dp_atual, dp_passagem_notas[k - 1][r1][r2] + pontuacao_atual);
// Caso base para o ponto inicial (1,1) para evitar depender de k-1 com índices inválidos
if (k == 2 && r1 == 1 && r2 == 1) {
estado_dp_atual = pontuacoes_grade_notas[1][1];
}
}
}
}
// O resultado final é quando ambas as pessoas chegam em (num_linhas, num_colunas)
std::cout << dp_passagem_notas[num_linhas + num_colunas][num_linhas][num_linhas] << std::endl;
return 0;
}