Python - problema de matrices

Tienes que poner un gasoducto a través de la gran ciudad X. La ciudad está representada por una cuadrícula de celdas N x N. Las columnas están numeradas del 1 al N de izquierda a derecha. Las filas están numeradas de 1 a N de arriba a abajo. Con el fin de sentar las tuberías hay que cavar en las células que la tubería atraviesa. Hay un costo involucrado en la excavación de cada célula. Su tarea consiste en minimizar el costo total de la excavación de las células.

Además tubería se debe colocar de columna de la izquierda (columna 1) a la columna derecha (columna N) de la ciudad que satisface las siguientes condiciones:

Desde la ciudad se encuentra en medio de un postre que no importa desde qué fila las tuberías comienza y termina. es decir, la tubería debe partir de cualquier célula de la columna 1 y debe terminar en cualquier celda de la columna N.

Cuando la tubería entre en la columna i (1 <= i <N), la tubería se puede colocar a la columna i + 1, utilizando una de las formas siguientes: (digamos tubería entra en la columna i en la fila j)

Coloque la tubería hacia arriba cualquier número de células (decir d) dentro de los límites de la ciudad y pasar a la columna i + 1 en la fila jd. d + células es decir, 1 en la columna i se cavaron hasta
Coloque la tubería hacia abajo cualquier número de células (decir d) dentro de los límites de la ciudad y pasar a la columna i + 1 en la fila j + d + 1 morir celdas de la columna 1 se cavaron hasta
Coloque la tubería a la columna i + 1 a la celda actual. es decir, sólo 1 célula se cavó en la columna i
Tarea
Dada la excavación de los costos para cada celda en la ciudad, encontrar el costo mínimo para la colocación de la tubería de la columna 1 a la columna N.

1 <= N <= 1000
0 <= costo de la excavación de la celda en la columna y la fila i j, c (i, j) <= 1000000