In a previous article, we discussed dynamic programming, which is a method to solve a larger problem by building up a solution solving smaller subproblems. It uses optimal substructure.
In this article, we are going to focus on another hot topic: backtracking.
Backtracking is a general algorithm for finding all or some solutions to a computational problem that incrementally builds candidates to the solutions while abandoning each partial candidate (backtracks). A partial candidate is abandoned either because it cannot possibly be completed to a valid solution or because the problem needs to find all valid solutions.
What are the differences between dynamic programming and backtracking? …
Roman numerals are a numeral system that originated from ancient Rome. It remains used today in some occasions. Modern usage of Roman numerals employs seven symbols, each is assigned an integer value:
A Roman numeral is composed with upper cases of MDCLXVI. It is written with the largest symbol at the left and the smallest symbol at right, consist with Arabic numerals. For example, MDCLXVI stands for 1666
(1000 + 500 + 100 + 50 + 10 + 5 + 1). …
After discussing how to prepare string manipulation interview questions, we are going to focus on another hot topic: dynamic programming.
Dynamic programming is a method to solve a larger problem by building up a solution to solving smaller subproblems.
An iterative implementation, eager and pre-caching, is usually preferred because it takes less time and memory. However, dynamic programming with iteration is harder to think through.
An iterative implementation is also called tabulation. …