最少加号问题 - DP表格演示

示例：s = "12", n = 3

目标： 在字符串 "12" 中插入最少的加号，使表达式结果等于 3

---

初始状态

dp[0][0] = 0  (0个字符，和为0，需要0个加号)
其他所有 dp[i][j] = INF (不可达)

初始表格

i\j	0	1	2	3
0		INF
1	INF
2
3

说明：

• i 表示已处理的字符数（前i个字符）
• j 表示当前的和
• 值表示达到该状态需要的最少加号数

---

第1轮：i=0, j=0（从位置0开始，当前和=0）

处理： 枚举从位置0开始的所有可能数字

步骤1.1：k=0，取字符 '1'

• v = 1（数字值）
• nex = 0 + 1 = 1（新的和）
• cnt = dp[0][0] = 0（当前加号数）
• i=0，所以不需要加号，cnt = 0
• 更新：dp[1][1] = min(INF, 0) = 0

步骤1.2：k=1，取字符 '1' 和 '2'，组成 "12"

• v = 1*10 + 2 = 12（数字值）
• nex = 0 + 12 = 12（新的和）
• cnt = dp[0][0] = 0
• i=0，所以不需要加号，cnt = 0
• 更新：dp[2][12] = min(INF, 0) = 0

第1轮后的表格

i\j	0	1	2	3
0		INF	INF
1	INF	0
2		INF
3

变化说明：

• dp[1][1] = 0：前1个字符（"1"），和为1，需要0个加号
• dp[2][12] = 0：前2个字符（"12"），和为12，需要0个加号

---

第2轮：i=1, j=1（从位置1开始，当前和=1）

处理： 枚举从位置1开始的所有可能数字

步骤2.1：k=1，取字符 '2'

• v = 2（数字值）
• nex = 1 + 2 = 3（新的和）✓ 达到目标！
• cnt = dp[1][1] = 0（当前加号数）
• i=1 > 0，所以需要加号，cnt = 0 + 1 = 1
• 更新：dp[2][3] = min(INF, 1) = 1 ✓

第2轮后的表格

i\j	0	1	2	3
0		INF	INF	INF
1	INF	0
2		INF		1 ✓
3				INF

变化说明：

• dp[2][3] = 1：前2个字符（"12"），和为3，需要1个加号
• 对应方案："1+2" = 3

---

最终结果

检查： dp[2][3] = 1（不是INF）

输出： 1

方案： "1+2" = 3，需要1个加号

---

完整DP表格（最终状态）

i\j	0	1	2	3
0		INF	INF	INF
1	INF	0
2		INF		1 ✓
3				INF

---

示例2：s = "303", n = 6

目标： 在字符串 "303" 中插入最少的加号，使表达式结果等于 6

初始表格（n=6，需要更多列）

i\j	0	1	2	3	4	5	6
0		INF
1	INF
2
3
4

---

第1轮：i=0, j=0

步骤1.1：k=0，取字符 '3'

• v = 3
• nex = 0 + 3 = 3
• cnt = 0（i=0，不需要加号）
• 更新：dp[1][3] = 0

步骤1.2：k=1，取字符 "30"

• v = 3*10 + 0 = 30
• nex = 0 + 30 = 30（超过n=6，但继续记录）
• cnt = 0
• 更新：dp[2][30] = 0（虽然超过6，但算法会记录）

步骤1.3：k=2，取字符 "303"

• v = 30*10 + 3 = 303（超过n=6，break）

第1轮后的表格

i\j	0	1	2	3	4	5	6
0		INF		INF	INF
1	INF			0
2				INF
3
4

---

第2轮：i=1, j=3（从位置1开始，当前和=3）

步骤2.1：k=1，取字符 '0'

• v = 0
• nex = 3 + 0 = 3
• cnt = dp[1][3] = 0，i=1>0，所以 cnt = 0 + 1 = 1
• 更新：dp[2][3] = 1

步骤2.2：k=2，取字符 "03"

• v = 0*10 + 3 = 3（前导零不影响，03=3）
• nex = 3 + 3 = 6 ✓ 达到目标！
• cnt = dp[1][3] = 0，i=1>0，所以 cnt = 0 + 1 = 1
• 更新：dp[3][6] = min(INF, 1) = 1 ✓

第2轮后的表格

i\j	0	1	2	3	4	5	6
0		INF		INF	INF		INF
1	INF			0
2				1
3				INF			1 ✓
4							INF

变化说明：

• dp[3][6] = 1：前3个字符（"303"），和为6，需要1个加号
• 对应方案："3+03" = 3 + 3 = 6

---

最终结果

检查： dp[3][6] = 1（不是INF）

输出： 1

方案： "3+03" = 3 + 3 = 6，需要1个加号

---

完整DP表格（最终状态）

i\j	0	1	2	3	4	5	6
0		INF		INF	INF		INF
1	INF			0
2				1
3				INF			1 ✓
4							INF

---

示例3：s = "99999", n = 45

目标： 在字符串 "99999" 中插入最少的加号，使表达式结果等于 45

关键状态转移

第1轮：i=0, j=0

• k=0: v=9, dp[1][9] = 0
• k=1: v=99, dp[2][99] = 0（超过45，但继续）
• k=2: v=999, 超过45，break

第2轮：i=1, j=9

• k=1: v=9, nex=9+9=18, dp[2][18] = 1
• k=2: v=99, nex=9+99=108, 超过45，break

第3轮：i=2, j=18

• k=2: v=9, nex=18+9=27, dp[3][27] = 2
• k=3: v=99, nex=18+99=117, 超过45，break

第4轮：i=3, j=27

• k=3: v=9, nex=27+9=36, dp[4][36] = 3
• k=4: v=9, nex=27+9=36（重复）

第5轮：i=4, j=36

• k=4: v=9, nex=36+9=45 ✓ 达到目标！
• dp[5][45] = 4 ✓

最终表格（关键状态）

i\j	0	9	18	27	36	45
0		INF	INF	INF	INF	INF
1	INF	0
2		INF	1
3			INF	2
4				INF	3
5					INF	4 ✓

方案： "9+9+9+9+9" = 45，需要4个加号

---

DP表格理解要点

1. 行（i）：表示已处理的字符数（前i个字符）

2. 列（j）：表示当前的和

3. 值：达到该状态需要的最少加号数

4. 转移规则：

   • 从 dp[i][j] 出发
   • 枚举下一个数字 s[i...k]
   • 更新 dp[k+1][j+v]
   • 如果 i > 0，加号数+1

5. 最终答案：dp[len][n]（使用所有字符，和为n的最少加号数）

---

算法执行流程总结

初始化：dp[0][0] = 0

对于每个位置 i (0 到 len-1):
    对于每个可能的和 j (0 到 n):
        如果 dp[i][j] 可达:
            枚举从位置 i 开始的所有数字 s[i...k]:
                计算数字值 v
                如果 v + j <= n:
                    更新 dp[k+1][j+v] = min(dp[k+1][j+v], dp[i][j] + (i>0?1:0))

答案：dp[len][n]

---

可视化流程图

初始状态: dp[0][0] = 0
    ↓
处理位置0: 枚举数字 "1", "12"
    ↓
更新: dp[1][1] = 0, dp[2][12] = 0
    ↓
处理位置1: 从 dp[1][1] 出发，枚举数字 "2"
    ↓
更新: dp[2][3] = 1  ✓ (达到目标)
    ↓
答案: dp[2][3] = 1

---

关键观察

1. 状态转移是逐步的：从 dp[0][0] 开始，逐步填充表格
2. 每个状态只被更新一次或多次取最小值：保证找到最优解
3. 剪枝优化：如果 v > n 或 j+v > n，提前退出
4. 前导零自动处理：通过 v = v*10 + digit 自动处理，03 = 3