Posts about Dynamic Programming

1105. Filling Bookcase Shelves [Dynamic Programming]


This post aims to describe the solution for 1105. Filling Bookcase Shelves based on the solution by a respectful coder Hexadecimal. This problem could be solved by dynamic programming.


We have a sequence of books: the i-th book has thickness books[i][0] and height books[i][1].

We want to place these books in order onto bookcase shelves that have total width shelf_width.

We choose some of the books to place on this shelf (such that the sum of their thickness is <= shelf_width), then build another level of shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.

Note again that at each step of the above process, the order of the books we place is the same order as the given sequence of books. For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.

Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

1039. Minimum Score Triangulation of Polygon

Problem Setting

Given N, consider a convex N-sided polygon with vertices labelled A[0], A[i], ..., A[N-1] in clockwise order.

Suppose you triangulate the polygon into N-2 triangles. For each triangle, the value of that triangle is the product of the labels of the vertices, and the total score of the triangulation is the sum of these values over all N-2 triangles in the triangulation.

Return the smallest possible total score that you can achieve with some triangulation of the polygon.

Source: LeetCode link


The solution is based on dynamic programming like below. This gif is explained in the last part.


1036. Escape a Large Maze

Problem Setting

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves

Link for Problem: leetcode

Example 1:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]

Output: false

Explanation: The target square is inaccessible starting from the source square, because we can't walk outside the grid.

Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]

Output: true


Because there are no blocked cells, it's possible to reach the target square.

1035. Uncrossed Lines

Problem Setting

We write the integers of A and B (in the order they are given) on two separate horizontal lines.

Now, we may draw a straight line connecting two numbers A[i] and B[j] as long as A[i] == B[j], and the line we draw does not intersect any other connecting (non-horizontal) line.

Return the maximum number of connecting lines we can draw in this way.

Link for Problem: leetcode

Example 1:


Input: A = [1,4,2], B = [1,2,4]

Output: 2

Explanation: We can draw 2 uncrossed lines as in the diagram. We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.

1000. Minimum Cost to Merge Stones

Problem Setting

There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Variable Type Description
stones list an array of stones with the merging cost
K int the maximum number of consecutive piles

Interactive Python Execution

Pythontutor is an awesome website which allows us to execute the code and visualize the flow of the code and variables taking account into data structure and stored values.

In [1]:
from IPython.display import IFrame
IFrame(",%20A,%20K%29%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20len%28A%29%0A%20%20%20%20%20%20%20%20if%20%28N%20-%201%29%20%25%20%28K%20-%201%29%3A%20return%20-1%0A%20%20%20%20%20%20%20%20INF%20%3D%20float%28'inf'%29%0A%20%20%20%20%20%20%20%20memo%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20prefix%20%3D%20%5B0%5D%20%23%20prefix%20sum%0A%20%20%20%20%20%20%20%20for%20x%20in%20A%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prefix.append%28prefix%5B-1%5D%20%2B%20x%29%0A%20%20%20%20%20%20%20%20def%20dp%28i,%20j,%20m%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20%28j%20-%20i%20%2B%201%20-%20m%29%20%25%20%28K%20-%201%29%3A%20return%20INF%20%20%23%20optimize%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20%28i,%20j,%20m%29%20in%20memo%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20memo%5Bi,%20j,%20m%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20i%20%3D%3D%20j%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%200%20if%20m%20%3D%3D%201%20else%20INF%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20m%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20dp%28i,%20j,%20K%29%20%2B%20prefix%5Bj%20%2B%201%5D%20-%20prefix%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20INF%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20mid%20in%20range%28i,%20j,%20K%20-%201%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20min%28res,%20dp%28i,%20mid,%201%29%20%2B%20dp%28mid%20%2B%201,%20j,%20m%20-%201%29%29%0A%20%20%20%20%20%20%20%20%20%20%20%20memo%5Bi,%20j,%20m%5D%20%3D%20res%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20res%0A%20%20%20%20%20%20%20%20res%20%3D%20dp%280,%20N%20-%201,%201%29%0A%20%20%20%20%20%20%20%20return%20res%20if%20res%20%3C%20INF%20else%200%0A%20%20%20%20%20%20%20%20%0Astones%20%3D%20%5B3,5,1,2,6%5D%0AK%20%3D%203%0As%20%3D%20Solution%28%29%0As.mergeStones%28stones,%20K%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false", width=1000, height=500)