有难度，dp状态不好想。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) /*************** Program Begin **********************/ static const int INF = 1000000000; static const int MAX_N = 50; static const int MAX_OP = 450; int dp[MAX_N + 1][MAX_OP + 1][2]; class CombinationLockDiv2 { public: int N; vector d; int rec(int p, int x, int up ) { int & res = dp[p][x][up]; if (p == N) { // base case res = 0; return res; } if (res != -1) { return res; } res = INF; for (int i = 0; i <= 1; i++) { for (int y = 0; y <= MAX_OP; y++) { if (0 == i) { // down if (d[p] - y % 10 != 0) { // invalid continue; } } else { // up if ( (d[p] + y) % 10 != 0 ) { // invalid continue; } } if (i == up) { // not necessary open new intervals res = min(res, max(y - x, 0) + rec(p + 1, y, i) ); } else { // must open y new intervals res = min(res, y + rec(p + 1, y, i) ); } } } return res; } int minimumMoves(string s, string t) { this->N = s.size(); d.resize(this->N); for (int i = 0; i < this->N; i++) { if (s[i] >= t[i]) { d[i] = s[i] - t[i]; } else { d[i] = s[i] + 10 - t[i]; } } memset(dp, -1, sizeof(dp)); return rec(0,0,0); } }; /************** Program End ************************/