算法
start->end
代入本题视角:
改变第i位,并不会影响到第i位右边的数
所以我们可以从右往左依次使start[i]=end[i]
有 进位-退位-不进不退 三种方式使start[i]=end[i]
其中 进位和退位会影响到i-1 也就是第i-1位上+1 -1的事情
现在定义f[i][0,1,2]分别表示第i位start[i]=end[i]的三种方式的最优解
对于f[i][0,1,2]的第i位,会受到f[i+1][0,1,2] 即是否进退位的影响
三种情况进行讨论 取最优
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5 + 9;
int n, f[N][3];
int main() {
cin >> n;
string start, end;
cin >> start >> end;
//我觉得无论是 进位-退位-不进不退 都用的是y与x相减,所以没必要 -'0'取出来
f[n - 1][0] = abs(start[n - 1] - end[n - 1]); //f[i][0] 表示第i位不通过进位或者退位使start[i]=end[i]
f[n - 1][1] = end[n - 1] - start[n - 1] + 10; //f[i][1] 表示第i位通过进位使start[i]=end[i]
f[n - 1][2] = start[n - 1] - end[n - 1] + 10; //f[i][2] 表示第i位通过退位使start[i]=end[i]
for(int i = n - 2; i >= 0; i--) {
//f[i][0,1,2]都可以通过f[i+1][0,1,2]转移过来,取小
char x = start[i], y = end[i];
f[i][0] = f[i + 1][0] + abs(x - y);
f[i][0] = min(f[i + 1][1] + abs(x + 1 - y), f[i][0]);
f[i][0] = min(f[i + 1][2] + abs(x - 1 - y), f[i][0]);
f[i][1] = f[i + 1][0] + (10 - x + y);
f[i][1] = min(f[i + 1][1] + (9 - x + y), f[i][1]);
f[i][1] = min(f[i + 1][2] + (11 - x + y), f[i][1]);
f[i][2] = f[i + 1][0] + (x + 10 - y);
f[i][2] = min(f[i + 1][1] + (x + 11 - y), f[i][2]);
f[i][2] = min(f[i + 1][2] + (x + 9 - y), f[i][2]);
}
//从右往左,对于f[i][0,1,2]依次使 i(包含)及其右边 使得start[i]=end[i]
//那么最后的答案就是 f[0][0] f[0][1] f[0][2] 取小
cout << min(f[0][0], min(f[0][1], f[0][2])) << endl;
return 0;
}
```