# Concise C++ Dp solution with explaination

• The base case is that dp[i][j] can be based on any valid dp[i-1][z] plus the min distance between z and j.

``````class Solution {
public:
int findRotateSteps(string ring, string key) {
vector<vector<int>> dp(key.size(),vector<int>(ring.size(),INT_MAX));
//base case
for(int i=0;i<ring.size();i++){
if(key[0]==ring[i]){
dp[0][i]=min(i,(int)ring.size()-i);  //i is the distance the ring move to right, ring.size()-i is the ring move to left
dp[0][i]++;    //click button
}
}

//general case
for(int i=1;i<key.size();i++){
for(int j=0;j<ring.size();j++){
if(key[i]==ring[j]){
for(int z=0;z<ring.size();z++){
if(dp[i-1][z]!=INT_MAX){
int distance= j>z?min(j-z,(int) (ring.size()-j+z)):min(z-j,(int)(ring.size()-z+j));
dp[i][j]=min(dp[i][j],dp[i-1][z]+distance);
}
}
dp[i][j]++;
}
}
}
int res=INT_MAX;
for(int i=0;i<ring.size();i++){
res=min(res,dp[key.size()-1][i]);
}
return res;
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.