✅3D Dp | ✅Simple Explanation | ✅C++
IntuitionThe intuition is pretty simple. We will have to use both hands as our states for the dynamic programming approach. It is optimal to place the firstHand
# Intuition

The intuition is pretty simple. We will have to use both hands as our states for the dynamic programming approach. It is optimal to place the `firstHand` where the first character is. We will represent the position of `secondHand` as `-1`.  

Now, inside the recursive function, we pass the `1th` index, as `firstHand` is already at the `0th` index.  

Inside the function, we first find the destination `to`, which is `str[i] - 'A'`.  
We calculate the cost of moving from `firstHand` to `to`, and from `to` to `secondHand`, and return the minimum among them.  

To **memoize**, we keep the state for:
- The position of `firstHand`
- The position of `secondHand`
- The current index `i`

### **How to calculate the cost?**  
- Dividing by `6` gives us the row number.
- Taking mod `6` gives us the column number.  
- Using **Manhattan Distance**, the cost formula is:  
  \[
  {cost} = |r_1 - r_2| + |c_1 - c_2|
  \]

---

# Approach

1. Initialize `firstHand` at `word[0] - 'A'` and `secondHand` at `-1`.
2. Use recursion with memoization to compute the minimum cost:
   - Move `firstHand` to `to` and recursively calculate the cost.
   - Move `secondHand` to `to` and recursively calculate the cost.
   - Store the result in the `dp` table.
3. Use a **3D DP table** (`dp[i][firstHand][secondHand]`) to store results.
4. Return the **minimum** among both choices.

---

# Complexity

- **Time Complexity:**  
  Since each state is defined by `(i, firstHand, secondHand)`, and there are at most **26** letters,  
  the complexity is **\(O(N * 26 * 26)\)** which is approximately **\(O(N)\)**.

- **Space Complexity:**  
  The `dp` table takes **\(O(N * 26 * 26)\)** space, which simplifies to **\(O(N)\)**.

---

# Code

```cpp


class Solution {
public:
    int getCost(int a, int b) {
        return a == -1 ? 0 : abs(a / 6 - b / 6) + abs(a % 6 - b % 6);
    }

    int solve(string& str, int i, int firstHand, int secondHand,
              vector<vector<vector<int>>>& dp) {
        if (i >= str.size())
            return 0;

        if (dp[i][firstHand + 1][secondHand + 1] != -1)
            return dp[i][firstHand + 1][secondHand + 1];

        int to = str[i] - 'A';

        int cost1 =
            solve(str, i + 1, to, secondHand, dp) + getCost(firstHand, to);
        int cost2 =
            solve(str, i + 1, firstHand, to, dp) + getCost(secondHand, to);

        return dp[i][firstHand + 1][secondHand + 1] = min(cost1, cost2);
    }

    int minimumDistance(string word) {
        int n = word.size();
        vector<vector<vector<int>>> dp(
            n,
            vector<vector<int>>(
                27, vector<int>(27, -1)));
        return solve(word, 1, word[0] - 'A', -1, dp);
    }
};

['String', 'Dynamic Programming', 'C++']