Presentación:

En esta sesión vamos a plantear algunos ejercicios que pueden ser resueltos aplicando la técnica de programación dinámica de diseño de algoritmos que fue introducida en una sesión anterior. Vamos a ir introduciendo ejercicios que irán siendo progresivamente más complejos, no por su dificultad, sino porque para su resolución vamos a tener que diseñar algoritmos que combinan no solo la técnica de programación dinámica pura sino también otros "ajustes" más ad-hoc para el problema concreto.

Cada uno de estos ejercicios propuestos llevará un esquema semejante: comenzaremos planteando el problema dando la referencia a la página del juez on-line donde se encuentra su enunciado. Después haremos un breve análisis de las características del problema y se irán proponiendo sucesivamente pistas sobre su resolución hasta llegar al listado del programa que lo resuelve. Se recomienda reflexionar un poco tras cada una de estas pistas antes de leer las siguientes, y por supuesto mucho antes de ver la solución propuesta.

Ejercicios propuestos:

Ejercicio 7.1. Cálculo de coeficientes binomiales.

Ejercicio 7.2. Descomposición de dinero.

Ejercicio 7.3. Submatriz de suma máxima.

Ejercicio 7.4. Mayor submatriz de unos.

Olimpiada de programación - Facultad de Informática - Universidad de Murcia