Dynamic Programming 面试题与答案
问题 26. Arithmetic Slices
A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. Return the total number of arithmetic slices in the array.
Example:
Input: [1, 2, 3, 4], Output: 3 (three arithmetic slices: [1, 2, 3], [2, 3, 4], [1, 2, 3, 4])
问题 27. Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Matrix: [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]], Output: 4
问题 28. Word Ladder II
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequences from beginWord to endWord.
Example:
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"], Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
问题 29. Paint House
There are a row of n houses, each house can be painted with one of the three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
Example:
Costs: [[17, 2, 17], [16, 16, 5], [14, 3, 19]], Output: 10 (paint the first house blue, the second house green, and the third house blue)
问题 30. Number of Dice Rolls With Target Sum
You have d dice, and each die has f faces numbered 1 to f. Return the number of possible ways (out of f^d total ways) to roll the dice so the sum of the face-up numbers equals target.
Example:
d = 2, f = 6, target = 7, Output: 6 (possible rolls: [1,6], [2,5], [3,4], [4,3], [5,2], [6,1])
用户评价最有帮助的内容：