我也来伐梯阶！

题解

我们可以把问题理解成：

要么直接凑出 n，要么多付一些钱再找零。

例如：

$$36=40-4$$

所以只需要 4 张 10 元和 4 张 1 元，一共 8 张。

1. 从个位开始考虑

对于当前数字 d：

不进位

直接支付这一位：

$$d$$

张纸币。

进位

把这一位变成 10，然后找回 10-d：

$$10-d$$

张纸币。

所以这一位有两种选择：

不进位：d
进位：10-d

显然选择后者更优。

---

2. 但是进位会影响下一位

例如：

36

个位选择进位：

40 - 4 = 36

那么十位就会多出一个 1。

所以我们从低位到高位处理，只需要记录：

carry = 0：前面没有进位
carry = 1：前面有进位

每一位只有两个状态，直接 DP。

---

3. DP

设：

dp[0]

表示处理到当前位，没有进位的最小纸币数。

dp[1]

表示处理到当前位，有进位的最小纸币数。

对于当前数字 d，枚举当前的 carry 和下一位的 carry。

如果下一位不进位，那么这一位需要处理：

$$d+carry$$

张。

如果下一位进位，那么这一位相当于：

$$10-(d+carry)$$

张找零。

因此直接枚举即可。

最后多处理一位 0，把最高位的进位消掉。

---

4. 代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;

    const long long INF=1e18;
    long long dp[2]={0,INF};

    for(int i=s.size()-1;i>=0;i--){
        int d=s[i]-'0';
        long long ndp[2]={INF,INF};

        for(int c=0;c<2;c++){
            // 不进位
            ndp[0]=min(ndp[0],dp[c]+d+c);

            // 进位
            if(d+c<=9)
                ndp[1]=min(ndp[1],dp[c]+10-d-c);
        }

        dp[0]=ndp[0];
        dp[1]=ndp[1];
    }

    // 处理最高位的进位
    dp[0]=min(dp[0],dp[1]+1);

    cout<<dp[0]<<'\n';
}

5. 复杂度

设 n 有 L 位。

每一位只计算两种状态，所以：

$$O(L)$$

空间：

$$O(1)$$