¿Cómo resolver BRTREE? No puedo obtener la relación de recurrencia que puede resolver el problema. Además, ¿cómo puedo obtener fácilmente la relación de recurrencia para cualquier problema de este tipo?

No construimos el árbol. La edad de un nodo determina todo lo que le sucede. Su pan es igual a su edad y generará nuevos nodos cero durante los primeros K años. Entonces podemos limitarnos a contar el número de nodos de diferentes edades.
Construyamos una secuencia [matemática] x_0, x_1, \ puntos [/ matemática], donde [matemática] x_i [/ matemática] es el número de nodos generados en el año [matemático] i [/ matemático].
[matemáticas] x_0 = 1 [/ matemáticas] y con cada año agregamos un número. Teniendo toda la secuencia [matemáticas] x_0, x_1, \ puntos, x_n [/ matemáticas], la escaneamos y calculamos la cantidad total de pan.
¿Cuál es el valor de [math] x_i [/ math]? Cada nodo que no sea anterior a [matemática] K [/ matemática] genera un nuevo nodo. Entonces, es la suma de los elementos precedentes [matemática] K [/ matemática].
Una implementación sencilla proporciona el algoritmo [math] O (N \ cdot K) [/ math].
¿Podemos calcularlo más rápido? ¡Seguro!
Para mejorar el rendimiento, mantenga una variable con la suma de los últimos elementos [math] K [/ math]. Con cada paso, agregue un elemento nuevo y reste uno antiguo. Esto da solución [matemática] O (N) [/ matemática].
¿Podemos hacerlo más rápido? Sí, pero se vuelve más complicado y realmente no es necesario. Si [math] K \ ge 2 [/ math], el número de nodos crece rápidamente y el peso máximo posible se alcanzará en menos de 50 años. Los casos en que [matemática] K = 0 [/ matemática] o [matemática] K = 1 [/ matemática] se pueden manejar fácilmente por separado.