目录
题目
动态规划思路
一开始，通过题意可以发现，修改左边位的值不会影响右边的值，因此我们可以考虑从最右边开始向前枚举，进行修改。
（错误思想开始）一开始，我想到用线性Dp。用f[i]表示，从第n位开始，向前 i 位成为y的所有方案。
注：不进位不退位就是直接在0~9之内相加减；进位就是向上加，超过10需要进位；退位就是向下减，减到0需要下一位退位。
因此：状态计算分为三种：
1、
2、 只考虑两种情况，一是不进位也不退位，二是退位（因为进位必会在还没加到10时就到y）
-
(这里还要考虑退位的问题）
3、 也考虑两种情况，一是不进位也不退位，二是进位（因为退位必会在还没减到0时就到y）
(这里还要考虑进位的问题）
然后用一个数组 来记录每次的进位还是退位。
（问题）但是，写完之后发现，好像写成了贪心的方式，每次都只取当前所有可能的最优解，然后进行计算。我们是否能保证每一位都选最优解然后求解最终的最优解，能否保证当前这位的最优解是能从上一位最优解传递过来？其二一个问题，如果，不能保证是不进位不退位还是进位或者退位是最优解。
太菜了只能说还是，参考大佬的文章AcWing 5408. 保险箱（状态机DP） - AcWing
（正确思想）使用状态机DP。因为每一种方式（即不进位不退位，进位向上加，退位）都可能是最优解，每一位的最优解都需要从这三种状态中求解当前为这三种状态的最优解。意思就是，这一位选择不进位不退位可以从上一位的不进位不退位，进位，退位三种状态中传递过来。不是直接去三种最优就传递给下一位！
（正片开始）分析：
使用 来进行状态表示
表示当前这位不进位不退位，可以从前三种状态
转移过来。具体
，取min。
+1 是因为上一位进位，x[i]+1；-1 是因为上一位退位，x[i]-1。
表示当前这位进位，同样可从前一位的三种状态
，取min。
-1 是因为上一位进位，这一位可以少加一个1；+1是因为上一位退位，这一位要多加一个1。
表示当前这位退位，同样可从前一位的三种状态
，取min。
+1 是因为上一位进位，这一位要多减一个1；-1是因为上一位退位，这一位可以少减一个1。
代码
很多细节，注释中有解释
import java.io.*;
import java.util.*;
class Main{
static int N = 100010;
static int n;
static int[] x = new int[N];
static int[] y = new int[N];
static int[][] f = new int[N][3]; //0 表示既不进位也不退位， 1 表示进位（即向上加），2 表示退位（即向下减）
static int[] e = new int[N];
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(in.readLine());
String x1 = in.readLine();
String y1 = in.readLine();
for(int i=0;i<n;i++){
x[i] = Integer.parseInt(String.valueOf(x1.charAt(i)));
y[i] = Integer.parseInt(String.valueOf(y1.charAt(i)));
}
f[n-1][0] = Math.abs(x[n-1]-y[n-1]);
f[n-1][1] = 10-x[n-1]+y[n-1];
f[n-1][2] = 10-y[n-1]+x[n-1];
for(int i=n-2;i>=0;i--){
// 不进位也不退位
f[i][0] = f[i+1][0]+Math.abs(x[i]-y[i]);
f[i][0] = Math.min(f[i][0],f[i+1][1]+Math.abs(x[i]-y[i]+1)); // 这里+1，是因为上一位进位了，那么x[i]就会变成x[i]+1
f[i][0] = Math.min(f[i][0],f[i+1][2]+Math.abs(x[i]-y[i]-1)); // 这里-1，是因为上一位退位了，那么x[i]就会变成x[i]-1
// 进位，向上加
f[i][1] = f[i+1][0]+Math.abs(10-x[i]+y[i]);
f[i][1] = Math.min(f[i][1],f[i+1][1]+10-x[i]+y[i]-1); // 如果上一位进位，这一位向上加就可以少加一次
f[i][1] = Math.min(f[i][1],f[i+1][2]+10-x[i]+y[i]+1); // 如果上一位退位，这一位向上加就要多加一次
// 退位，向下减
f[i][2] = f[i+1][0]+Math.abs(10-y[i]+x[i]);
f[i][2] = Math.min(f[i][2],f[i+1][1]+10-y[i]+x[i]+1); // 如果上一位进位，这一位向下减就要多减一次
f[i][2] = Math.min(f[i][2],f[i+1][2]+10-y[i]+x[i]-1); // 如果上一位退位，这一位向下减就可以少减一次
}
int res = Math.min(f[0][0],f[0][1]);
res = Math.min(res,f[0][2]);
System.out.println(res);
}
}贪心思路
然后我叒参考了一篇大佬的解析，使用贪心AcWing 5408. 保险箱-贪心（+势能分析） - AcWing