Aquí hay una solución de programación dinámica.
Si usamos solo los primeros enteros i del N dado, ¿cuál es la suma de los productos de estos enteros tomados j a la vez? Defina esto como f (i, j). Se nos ha pedido que encontremos f (N, k).
Ahora podemos intentar encontrar una recurrencia para f (i, j). Entre las formas de elegir j enteros entre los primeros i, algunos incluyen a [i] y el resto no. Si no se incluye un [i], los enteros j deben seleccionarse del primer i-1. Esto da una contribución de f (i-1, j) a la suma. Si se incluye un [i], los enteros j-1 deben elegirse del primer i-1. La contribución de todas las j-tuplas que involucran a [i] es, por lo tanto, un [i] × f (i-1, j-1). Juntos, esto nos da:
- ¿Por qué EPFL no produce grandes programadores que puedan descifrar entrevistas técnicas de compañías como Google, Facebook, Palantir, Amazon, etc.?
- ¿Cuál es la explicación y la prueba de la codiciosa solución en esta pregunta?
- ¿Cuáles son algunos proyectos que se pueden hacer para mejorar mi cartera de proyectos junto con mi currículum?
- ¿Qué proyectos de codificación debe hacer uno si él / ella está solicitando Google, FB, Microsoft, Twitter, Amazon, etc.?
- ¿Cuáles son algunos acertijos interesantes que se hacen en las entrevistas técnicas de programación informática?
f (i, j) = f (i-1, j) + a [i] f (i-1, j-1)
Con los casos base f (i, 0) = 1 para todos i y f (0, j) = 0 para j> 1, podemos calcular f (N, k) utilizando la recurrencia en el tiempo O (Nk).
PD: Este método es esencialmente el mismo que la respuesta de Christopher Chang . Piénsalo 🙂