Algorithm · C3.ai · Medium
You have a rectangular piece of sheet metal and a price table that assigns a value to each square whose side length is an integer. The goal is to divide the entire sheet into squares so that the sum of their prices is as large as possible. Every cut must run straight across the whole piece currently being cut, either horizontally or vertically, from one edge to the opposite edge; each cut splits a rectangle into two smaller rectangles, which can then be cut further. Be aware…