How to Approach Dp Problems Solved !!! -> Top Down  ->>>> Bottom Up (4 Solutions)
Start With Top Down Approach\nBelow I am Sharing My Approch\n\nint dp[301][27][27];\nclass Solution {\npublic:\n    int findPos(char a){\n        return a - \'A
**Start With Top Down Approach**\nBelow I am Sharing My Approch\n```\nint dp[301][27][27];\nclass Solution {\npublic:\n    int findPos(char a){\n        return a - \'A\';\n    }\n    int findCost(int from, int to){\n        if(from == 26) return 0;\n        int r1 = from/6;\n        int c1 = from%6;\n        int r2 = to/6;\n        int c2 = to%6;\n        return abs(r1 - r2) + abs(c1 - c2);\n    }\n    int solve(int index, int finger1, int finger2, string& word){\n        if(index == word.size()) return 0;\n        if(dp[index][finger1][finger2] != -1) return dp[index][finger1][finger2];\n        int newPos = findPos(word[index]);\n        int cost1 = findCost(finger1, newPos);\n        int cost2 = findCost(finger2, newPos);\n        return dp[index][finger1][finger2] = min(cost1 + solve(index + 1, newPos, finger2, word), cost2 + solve(index + 1, finger1, newPos, word));\n    }\n    int minimumDistance(string word) {\n        memset(dp, -1, sizeof(dp));\n        return solve(0, 26, 26, word);\n    }\n};\n```\nThis is a Brute Force Dp with no State Compression\n\n**Optimised Top Down**\n```\nint dp[301][27];\nclass Solution {\npublic:\n    int findPos(char a){\n        return a - \'A\';\n    }\n    int findCost(int from, int to){\n        if(from == 26) return 0;\n        int r1 = from/6;\n        int c1 = from%6;\n        int r2 = to/6;\n        int c2 = to%6;\n        return abs(r1 - r2) + abs(c1 - c2);\n    }\n    int solve(int index, int notMovingFinger, string& word){\n        if(index == word.size()) return 0;\n        if(dp[index][notMovingFinger] != -1) return dp[index][notMovingFinger];\n        int previouslyMovedFinger = index == 0 ? 26 : findPos(word[index - 1]);\n        int newPos = findPos(word[index]);\n        int cost1 = findCost(notMovingFinger, newPos);\n        int cost2 = findCost(previouslyMovedFinger, newPos);\n        return dp[index][notMovingFinger] = min(cost1 + solve(index + 1, previouslyMovedFinger, word), cost2 + solve(index + 1, notMovingFinger, word));\n    }\n    int minimumDistance(string word) {\n        memset(dp, -1, sizeof(dp));\n        return solve(0, 26, word);\n    }\n};\n```\n**Optimised Bottom up**\n```\nclass Solution {\npublic:\n    int findPos(char a){\n        return a - \'A\';\n    }\n    int findCost(int from, int to){\n        if(from == 26) return 0;\n        int r1 = from/6;\n        int c1 = from%6;\n        int r2 = to/6;\n        int c2 = to%6;\n        return abs(r1 - r2) + abs(c1 - c2);\n    }\n    int minimumDistance(string word){\n        int n = word.size();\n        vector<vector<long long>> dp(n + 1, vector<long long>(27, INT_MAX));\n        dp[0][26] = 0;\n        for(int i = 1; i < n + 1; i++){\n//             position of NotMoving finger ---> j\n            for(int j = 0; j < 27; j++){\n//                  position of Previously Moved finger ---> k;\n                int k = i == 1 ? 26 : findPos(word[i - 2]);\n                dp[i][k] = min(dp[i][k], findCost(j, findPos(word[i - 1])) + dp[i-1][j]);\n                dp[i][j] = min(dp[i][j], findCost(k, findPos(word[i - 1])) + dp[i-1][j]);\n            }\n        }\n        long long ans = INT_MAX;\n        for(int i = 0; i < 27; i++) ans = min(ans, dp[n][i]);\n        return ans;\n    }\n};\n```\n\n**Super optimised Bottom up**\n```\nclass Solution {\npublic:\n    int findPos(char a){\n        return a - \'A\';\n    }\n    int findCost(int from, int to){\n        if(from == 26) return 0;\n        int r1 = from/6;\n        int c1 = from%6;\n        int r2 = to/6;\n        int c2 = to%6;\n        return abs(r1 - r2) + abs(c1 - c2);\n    }\n    int minimumDistance(string word){\n        int n = word.size();\n        vector<long long> dp(27, INT_MAX);\n        dp[26] = 0;\n        for(int i = 1; i < n + 1; i++){\n            vector<long long> kp(27, INT_MAX);\n//             position of NotMoving finger ---> j\n            for(int j = 0; j < 27; j++){\n//                  position of Previously Moved finger ---> k;\n                int k = i == 1 ? 26 : findPos(word[i - 2]);\n                kp[k] = min(kp[k], findCost(j, findPos(word[i - 1])) + dp[j]);\n                kp[j] = min(kp[j], findCost(k, findPos(word[i - 1])) + dp[j]);\n            }\n            dp = kp;\n        }\n        long long ans = INT_MAX;\n        for(int i = 0; i < 27; i++) ans = min(ans, dp[i]);\n        return ans;\n    }\n};\n```\n
[]