动态规划帮我通关了《辐射4》
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 514. Freedom Trail | 🔴 |
The cover image of this article is from a mission scene in the game "Fallout 4":
This rotating disk is like a password mechanism. Notice the red pointer near the top center? By rotating the disk, you can point the pointer to different letters. Then, pressing the central button inputs the letter the pointer is pointing to.
By rotating the ring to make the pointer point to R, A, I, L, R, O, A, D in sequence and pressing the button each time, you can trigger the mechanism and open the door beside it.
As for why the password is these letters, the game's storyline provides hints, so we won't delve into that here.
So, what does this game scenario have to do with dynamic programming?
Let's ponder over this: Rotating the disk to input these letters is quite troublesome. What order would minimize the number of operations needed to rotate the disk?
Different methods of rotating the disk will require different numbers of operations.
For example, to align a letter with the pointer, you can rotate the disk clockwise or counterclockwise. Moreover, some letters may appear more than once. In the image above, the uppercase letter O appears three times on the disk. Which O should you align to minimize the overall number of operations?
As we've mentioned before, problems involving finding the maximum or minimum value are typically solved using dynamic programming algorithms, since dynamic programming is a type of optimization algorithm.
There is an algorithm problem on LeetCode based on this rotating disk game, classified as Hard. However, I solved it at first glance because I had previously thought about a very interesting real-life example that can be analogous to this problem. Let me introduce it briefly.
I used to practice several piano pieces by Liszt and Chopin. For those who haven't practiced piano, you might not know that practicing piano sheet music requires pre-determining the "fingering."
The notes on the staff go up and down, and the fingers of both hands must coordinate with each other. This means you need to decide which finger of which hand will play each note and write it down on the sheet.
For example, one of my favorite pieces is called "Liebesträume." Here is the sheet music I used when I first started learning:
The numbers above the notes represent the fingers: 1 for the thumb, 2 for the index finger, and so on. By practicing with the determined fingering repeatedly, you form muscle memory, and that's how you master a piece.
Fingering varies from person to person. For instance, someone with larger hands might let their middle finger cross over to the left of their thumb, while those with smaller hands might find it awkward. Thus, the same piece of music might have different fingerings for different people.
So, the question arises: How should I design the fingering to minimize the "awkwardness" of finger transitions, thereby maximizing the fluency of the performance?
Here, I utilized the dynamic programming algorithm technique: Isn't the switching of fingers just a state transition? Referring to the previous article Dynamic Programming Techniques Explained, as long as we clarify the "state" and "choices," we can solve this problem.
What is the state? The state is the "next note to be played" and the "current state of the hand."
The next note to be played is simply one of the 88 keys on the piano. The state of the hand is also straightforward: five fingers, each either pressed down or not, resulting in 2^5 = 32 possible states, which can be represented by 5 binary digits.
What are the choices? The choices are "which finger should play the next note," essentially exhausting all five fingers.
Of course, considering the current state of the hands, each choice has a corresponding cost, which varies from person to person, as mentioned earlier. Therefore, I need to customize a loss function for myself to calculate the "awkwardness" of switching between different fingerings.
Now, the problem becomes a standard dynamic programming problem. We need to make the choice with the least "awkwardness" based on the loss function to ensure the most fluid performance...
However, the time complexity of this algorithm is too high. Our analysis was only for a single note, but if we string notes into a melody, the time and space complexity need to be multiplied by the number of notes in the melody, which is quite large.
Moreover, this loss function is difficult to quantify. The difficulty of hitting the black and white keys on the piano varies, and the "awkwardness" can only be felt, which is somewhat imprecise...
Nevertheless, it's not necessary to calculate the fingering for the entire piece. It's sufficient to calculate the fingering for some complex sections, making this algorithm quite effective.
Having discussed these side topics, let's get to the main point. Today's topic is LeetCode problem #514 "Freedom Trail," which shares similarities with the piano fingering problem. If you can understand the piano example, you should be able to solve this algorithm problem quickly.
The problem gives you a string ring representing the characters on a circular disk (the pointer is at the 12 o'clock position, initially pointing to ring[0]), and a string key representing the string you need to input by rotating the disk. Your algorithm should return the minimum number of operations required to input this key (both rotating the disk by one position and pressing the button in the center of the disk count as one operation).
The function signature is as follows:
int findRotateSteps(String ring, String key);int findRotateSteps(string ring, string key);def findRotateSteps(ring: str, key: str) -> int:func findRotateSteps(ring string, key string) int {}var findRotateSteps = function(ring, key) {}For example, consider the given problem where the input is ring = "godding", key = "gd". The corresponding dial looks like this (uppercase is used for clarity, but the actual input strings are in lowercase):
We need to input key = "gd", and the algorithm should return 4.
Since the pointer is already at the letter "g", we can press the middle button directly. Then, we rotate the dial counterclockwise by two steps to point to the letter "d", and press the middle button again.
In this process, we press the button twice and rotate the dial by two steps, making a total of 4 operations. This is the minimum number of operations, so the algorithm should return 4.
First, let's make an equivalence: rotating the dial is the same as moving the pointer, right?
The original problem can be transformed to: the dial is fixed, and we can move the pointer; now we need to move the pointer and press the button to input the string corresponding to key with the minimum number of operations.
So, how can we solve this problem using dynamic programming techniques? Or, what are the "states" and "choices" in this problem?
The "state" is defined by "the current character to be input" and "the current position of the dial pointer".
To be more specific, the "state" is represented by two variables, i and j. We can use i to denote the character currently pointed to by the dial pointer (i.e., ring[i]), and j to denote the character that needs to be input (i.e., key[j]).
With this, we can write a dp function like this:
int dp(String ring, int i, String key, int j);int dp(string ring, int i, string key, int j);def dp(ring: str, i: int, key: str, j: int) -> int:func dp(ring string, i int, key string, j int) intvar dp = function(ring, i, key, j){}The definition of this dp function is as follows:
When the disk pointer is at ring[i], at least dp(ring, i, key, j) operations are needed to input the string key[j..].
Based on this definition, the problem essentially wants to calculate the value of dp(ring, 0, key, 0). Additionally, we can write the base case for the dp function:
int dp(String ring, int i, String key, int j) {
// base case, input is complete
if (j == key.length()) return 0;
// ...
}int dp(string ring, int i, string key, int j) {
// base case, input is completed
if (j == key.length()) return 0;
// ...
}def dp(ring: str, i: int, key: str, j: int) -> int:
# base case, input completed
if j == len(key):
return 0
# ...func dp(ring string, i int, key string, j int) int {
// base case, input is complete
if j == len(key) {
return 0
}
// ...
}var dp = function(ring, i, key, j) {
// base case, input completed
if (j === key.length) return 0;
// ...
};Next, let's think about how to make decisions based on the current state and how to transition between states.
"Decision" means "how to rotate the dial to get the desired character".
To be more specific, for the character key[j] we want to input, how can we rotate the dial to get this character?
For example, if the input is ring = "gdonidg", the current state of the dial is as shown below:
Assume the character we want to input is key[j] = "d". There are two "d" letters on the dial, and we can rotate the pointer either clockwise or counterclockwise. Therefore, there are four possible "decisions" to input the character "d". We need to choose the rotation method that requires the fewest operations.
The general code logic is as follows:
int dp(String ring, int i, String key, int j) {
// base case: input is complete
if (j == key.length()) return 0;
// make a choice
int res = Integer.MAX_VALUE;
for (int k : [字符 key[j] 在 ring 中的所有索引]) {
res = min(
把 i 顺时针转到 k 的代价,
把 i 逆时针转到 k 的代价
);
}
return res;
}int dp(string ring, int i, string key, int j) {
// base case: completed input
if (j == key.length()) return 0;
// make a choice
int res = INT_MAX;
for (int k : [字符 key[j] 在 ring 中的所有索引]) {
res = min(
把 i 顺时针转到 k 的代价,
把 i 逆时针转到 k 的代价
);
}
return res;
}def dp(ring: str, i: int, key: str, j: int) -> int:
# base case: input is complete
if j == len(key): return 0
# make a choice
res = float('inf')
for k in [字符 key[j] 在 ring 中的所有索引]:
res = min(
转到 k 顺时针的代价,
转到 k 逆时针的代价
)
return resfunc dp(ring string, i int, key string, j int) int {
// base case: completed input
if j == len(key) {
return 0
}
// make a choice
res := math.MaxInt64
for _, k := range [字符 key[j] 在 ring 中的所有索引] {
res = min(
转到 k 顺时针的代价,
转到 k 逆时针的代价
)
}
return res
}var dp = function(ring, i, key, j) {
// base case: input is complete
if (j === key.length) return 0;
// make a choice
var res = Infinity;
for (var k of [字符 key[j] 在 ring 中的所有索引]) {
res = Math.min(
把 i 顺时针转到 k 的代价,
把 i 逆时针转到 k 的代价
);
}
return res;
}Regarding whether it's clockwise or counterclockwise, it's actually quite easy to determine: just go the shorter way. But what about the two characters "d" on the dial? Can we still just go the shorter way?
No, because it depends on the character that needs to be input after key[i]. Let's take the same example:
If the input is key = "di", then even though the right "d" is closer, you should go to the left "d". This is because the left "d" is next to "i", resulting in the fewest overall operations.
So, how should we determine this? It's essentially about exhaustively listing all possibilities. Recursively call the dp function to calculate the overall cost for both choices, and then compare them.
That's about it for the explanation. Let's directly look at the final code:
class Solution {
// character -> index list
HashMap<Character, List<Integer>> charToIndex = new HashMap<>();
// memoization table
int[][] memo;
// main function
public int findRotateSteps(String ring, String key) {
int m = ring.length();
int n = key.length();
// initialize all memoization table entries to 0
memo = new int[m][n];
// record the mapping of characters to indices on the ring
for (int i = 0; i < ring.length(); i++) {
char c = ring.charAt(i);
if (!charToIndex.containsKey(c)) {
charToIndex.put(c, new LinkedList<>());
}
charToIndex.get(c).add(i);
}
// the disk pointer initially points to the 12 o'clock direction,
// start inputting key from the first character
return dp(ring, 0, key, 0);
}
// calculate the minimum number of operations when the disk pointer is at ring[i] and inputting key[j..]
int dp(String ring, int i, String key, int j) {
// base case: complete input
if (j == key.length()) return 0;
// check the memoization table to avoid overlapping subproblems
if (memo[i][j] != 0) return memo[i][j];
int n = ring.length();
// make choices
int res = Integer.MAX_VALUE;
// there may be multiple characters key[j] on ring
for (int k : charToIndex.get(key.charAt(j))) {
// number of pointer movements
int delta = Math.abs(k - i);
// choose clockwise or counterclockwise
delta = Math.min(delta, n - delta);
// move the pointer to ring[k], continue inputting key[j+1..]
int subProblem = dp(ring, k, key, j + 1);
// choose the minimum number of "overall" operations
// add one because pressing the button is also an operation
res = Math.min(res, 1 + delta + subProblem);
}
// store the result in the memoization table
memo[i][j] = res;
return res;
}
}class Solution {
// character -> index list
unordered_map<char, vector<int>> charToIndex;
// memoization
vector<vector<int>> memo;
// main function
public:
int findRotateSteps(string ring, string key) {
int m = ring.size();
int n = key.size();
// initialize all memoization to 0
memo = vector<vector<int>>(m, vector<int>(n, 0));
// record the mapping of characters to indices on the ring
for (int i = 0; i < ring.size(); i++) {
char c = ring[i];
if (!charToIndex.count(c)) {
charToIndex[c] = vector<int>();
}
charToIndex[c].push_back(i);
}
// the disk pointer initially points to the 12 o'clock direction,
// start inputting key from the first character
return dp(ring, 0, key, 0);
}
private:
// calculate the minimum number of operations when the disk pointer is at ring[i] and inputting key[j..]
int dp(const string& ring, int i, const string& key, int j) {
// base case: complete input
if (j == key.size()) return 0;
// check memoization to avoid overlapping subproblems
if (memo[i][j] != 0) return memo[i][j];
int n = ring.size();
// make choices
int res = INT_MAX;
// there may be multiple characters key[j] on ring
for (int k : charToIndex[key[j]]) {
// number of pointer movements
int delta = abs(k - i);
// choose clockwise or counterclockwise
delta = min(delta, n - delta);
// move the pointer to ring[k] and continue inputting key[j+1..]
int subProblem = dp(ring, k, key, j + 1);
// choose the option with the minimum "overall" number of operations
// add one because pressing the button is also an operation
res = min(res, 1 + delta + subProblem);
}
// store the result in memoization
memo[i][j] = res;
return res;
}
};class Solution:
def __init__(self):
# character -> index list
self.charToIndex = collections.defaultdict(list)
# memoization table
self.memo = None
# main function
def findRotateSteps(self, ring: str, key: str) -> int:
m = len(ring)
n = len(key)
# initialize the entire memoization table to 0
self.memo = [[0] * n for _ in range(m)]
# record the mapping of characters to indices on the ring
for i, c in enumerate(ring):
self.charToIndex[c].append(i)
# the disk pointer initially points to the 12 o'clock direction,
# start inputting key from the first character
return self.dp(ring, 0, key, 0)
# calculate the minimum number of operations when the disk pointer is at ring[i], inputting key[j..]
def dp(self, ring: str, i: int, key: str, j: int) -> int:
# base case: input completed
if j == len(key):
return 0
# check the memoization table to avoid overlapping subproblems
if self.memo[i][j] != 0:
return self.memo[i][j]
n = len(ring)
# make a choice
res = float('inf')
# there may be multiple characters key[j] on the ring
for k in self.charToIndex[key[j]]:
# number of pointer movements
delta = abs(k - i)
# choose clockwise or counterclockwise
delta = min(delta, n - delta)
# move the pointer to ring[k], continue inputting key[j+1..]
subProblem = self.dp(ring, k, key, j + 1)
# choose the option with the minimum total number of operations
# add one because pressing the button is also an operation
res = min(res, 1 + delta + subProblem)
# store the result in the memoization table
self.memo[i][j] = res
return res// main function
func findRotateSteps(ring string, key string) int {
m := len(ring)
n := len(key)
// initialize the memoization table
memo := make([][]int, m)
for i := range memo {
memo[i] = make([]int, n)
}
// initialize the mapping from character to indices
charToIndex := make(map[rune][]int)
for i, c := range ring {
charToIndex[c] = append(charToIndex[c], i)
}
var dp func(ring string, i int, key string, j int, memo [][]int, charToIndex map[rune][]int) int
dp = func(ring string, i int, key string, j int, memo [][]int, charToIndex map[rune][]int) int {
// base case: complete the input
if j == len(key) {
return 0
}
// check the memoization table to avoid overlapping subproblems
if memo[i][j] != 0 {
return memo[i][j]
}
n := len(ring)
// make a choice
res := math.MaxInt32
// there may be multiple characters key[j] on the ring
for _, k := range charToIndex[rune(key[j])] {
// number of times to move the pointer
delta := int(math.Abs(float64(k - i)))
// choose clockwise or counterclockwise
delta = min(delta, n - delta)
// move the pointer to ring[k] and continue inputting key[j+1..]
subProblem := dp(ring, k, key, j + 1, memo, charToIndex)
// choose the option with the least number of "overall" operations
// add one because pressing the button is also an operation
res = min(res, 1 + delta + subProblem)
}
// store the result in the memoization table
memo[i][j] = res
return res
}
// the disc pointer initially points to the 12 o'clock direction
// start inputting key from the first character
return dp(ring, 0, key, 0, memo, charToIndex)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}var findRotateSteps = function(ring, key) {
// character -> index list
let charToIndex = new Map();
// memoization
let memo;
// main function
function main(ring, key) {
let m = ring.length;
let n = key.length;
// initialize all memoization to 0
memo = Array.from({ length: m }, () => Array(n).fill(0));
// record the mapping of characters to indices on the ring
for (let i = 0; i < ring.length; i++) {
let c = ring.charAt(i);
if (!charToIndex.has(c)) {
charToIndex.set(c, []);
}
charToIndex.get(c).push(i);
}
// the disc pointer initially points to the 12 o'clock direction
// start inputting key from the first character
return dp(ring, 0, key, 0);
}
// calculate the minimum number of operations for the disc pointer at ring[i], inputting key[j..]
function dp(ring, i, key, j) {
// base case: complete input
if (j == key.length) return 0;
// check memoization to avoid overlapping subproblems
if (memo[i][j] != 0) return memo[i][j];
let n = ring.length;
// make a choice
let res = Infinity;
// there may be multiple characters key[j] on ring
for (let k of charToIndex.get(key.charAt(j))) {
// number of pointer movements
let delta = Math.abs(k - i);
// choose clockwise or counterclockwise
delta = Math.min(delta, n - delta);
// move the pointer to ring[k], continue inputting key[j+1..]
let subProblem = dp(ring, k, key, j + 1);
// choose the minimum number of "overall" operations
// add one because pressing the button is also an operation
res = Math.min(res, 1 + delta + subProblem);
}
// store the result in memoization
memo[i][j] = res;
return res;
}
return main(ring, key);
};