Comentário por Lúcio Cardoso
Xadrez
Conhecimento prévio necessário:
Seja $$(x,y)$$ o quadrado na linha $$x$$ e coluna $$y$$ do tabuleiro. Já que a cor do quadrado $$(1, 1)$$ é branca, a cor de cada quadrado $$(x,y)$$ pode ser encontrada baseando-se nos seguintes casos:
1. Se x e y tem a mesma paridade, a cor de $$(x,y)$$ é branca.
2. Se x e y tem paridades diferentes, a cor de $$(x, y)$$ é preta.
Como queremos encontrar a cor do $$(L,C)$$ (canto inferior direito), basta checar em qual dos casos o quadrado se encaixa, imprimindo sua respectiva cor. Segue o código para melhor entendimento.
https://gist.github.com/biacunha/df2b83b081862ed3b67134da54b33174
Escadinha
Conhecimento prévio necessário:
Perceba que uma escadinha é, na verdade, uma Progressão Aritmética (PA). Então, o problema se resume em encontrar a quantidade de PAs na sequência tais que nenhuma delas esteja totalmente contida em alguma outra,
e todas as PAs calculadas possuam o maior tamanho possível. Assim, para um índice $$i$$ (inicialmente 1), encontraremos o maior índice $$j$$ tal que a sequência de $$i$$ a $$j$$ seja uma PA, repetindo o processo novamente, ou seja, fazendo o novo indíce inical de uma escadinha sendo $$j$$, até que o último índice seja o próprio fim da sequência $$(n)$$. Segue o código para melhor entendimento.
https://gist.github.com/biacunha/91b9628eee13076c152f70e97f694fd3
Pirâmide
- Programação dinâmica (Aula 13)
Para cada linha $$i$$ da pirâmide com $$i$$ caixas numeradas por colunas de $$j$$ a $$j+i-1$$, a linha acima $$(i-1)$$ possui $$i-1$$ caixas consecutivas, ou com colunas desde $$j$$ a $$j+i-2$$, ou desde $$j+1$$ a $$j+i-1$$, já que, caso contrário, ao menos uma das caixas não possuiria uma respectiva caixa abaixo dela, na linha $$i$$. Assim, podemos utilizar uma função recursiva $$f(k, j)$$ para encontrar a resposta mínima do problema, representando a pirâmide com a linha de índice $$k$$ em sua base, e que por sua vez tem $$k$$ caixas consecutivas a partir da coluna $$j$$. Temos, assim, que:
1. O caso base da função pode ser tomado quando $$k = 1$$, já que a resposta neste caso é apenas o valor da caixa na linha $$1$$, coluna $$j$$.
2. Como a linha $$k$$ é a base da pirâmide, a soma de todos os valores das $$k$$ caixas desde a coluna $$j$$ até a coluna $$j+k-1$$ estará incluída na resposta de $$f(k, j)$$.
3. Pelas observações anteriores, há dois casos para a coluna inicial na linha $$k-1$$: ou $$j$$, ou $$j+1$$. Perceba que assim, a coluna final em tal linha está definida: será, respectivamente, $$j+k-2$$ ou $$j+k-1$$, já que a linha $$k-1$$ possui $$k-1$$ caixas. Como queremos a soma mínima possível dos valores das caixas, escolheremos o mínimo entre estes dois casos.
Podemos, então, finalmente montar a relação de recursão de $$f(k, j)$$:
Se $$k = 1$$, $$f(k, j) = caixa[1][j];$$
Senão, $$f(k, j) = s[k][j…j+k-1] + min(f(k-1, j), f(k-1, j+1))$$, onde $$s[x][a…b]$$ é a soma dos números na linha $$x$$ desde a coluna $$a$$ até a coluna $$b$$. No entanto, a complexidade da função é exponencial, e logo, não passa nas restrições do problema. Para tornar a complexidade aceitável, utilizaremos duas técnicas adicionais:
1. Podemos conseguir $$s[x][a..b]$$ em $$O(1)$$, com pré-cálculo em $$O(n²)$$, da seguinte maneira: Primeiro, vamos definir uma matriz $$soma[x][b]$$ como sendo a soma dos números na linha $$x$$ desde a coluna $$1$$ até a coluna $$b$$. Inicialmente, $$soma[x][0] = 0$$, para todo $$x$$ tal que $$1 <= x <= n$$. Então, $$soma[x][b] = soma[x][b-1]+caixa[x][b]$$, com $$1 <= b <= n$$. Portanto, é possível conseguir $$s[x][1…b]$$ em $$O(1)$$ após o pré-cálculo, já que $$s[x][a…b] = s[x][1…b]-s[x][1…(a-1)]$$, ou seja, $$s[x][a…b] = soma[x][b]-soma[x][a-1]$$.
2. Finalmente, usaremos uma matriz $$n*n$$ chamada $$dp[n][n]$$ que irá guardar todos os estados que já foram previamente calculados na recursão (essa técnica é conhecida como programação dinâmica). Assim, evitamos que um estado seja calculado mais de uma vez, tornando a complexidade da função $$O(n²)$$, já que $$1 <= k, j <= n$$. Obteremos então a resposta do problema chamando $$f(n, 1)$$.
Segue o código para melhor entendimento.
https://gist.github.com/biacunha/01e1787151b969cdd945590d55649f1e