Python Programs Dynamic Programming :
This Python file contains programs on Dynamic Programming,
The first question finds the longest ordered subsequences of a given numberic sequence.
The second program solves the given dynammic problem: Due to recent rains (I know it’s very rare here), water has pooled in various places in the campus, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('#') or dry land ('-'). A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. The problem is to figure out how many ponds have formed in the campus, given a diagram of the campus. The campus is represented by a grid represented by a list of N lines of characters separated by “,”. Each line contains M characters per line representing one row of the grid (campus). Each character is either '#' or '-'. The characters do not have spaces between them. Write a program to compute and return the number of ponds in the campus.
The third prigram solves the below job scheduling and deadline problem: A supermarket has a set ‘Prod’ of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=Σx∈Sellpx. An optimal selling schedule is a schedule with a maximum profit.