2919
选或不选
错误想法1
让dp[i] 表达当前当前i 被包进范围所需的最小修改
- 如果选当前
i的值进行增加，我们就不会再去在意之前两个值所需要多少了，而是在意前面的第三个值 - 如果不选的话，我们就得在意前二个的值了
- 总结则是
dp[i] = min(dp[i - 1], dp[i - 2], dp[i - 3] + max(k - i, 0))
为什么错
dp[i] 表达当前当前i 被包进范围所需的最小修改，但后面看前面的数并不能得到有用的信息，例如: [2,3,0,0,2], k = 4 我们的dp = [2,1,1,1,1] 我们会发现在最后一个数2时dp[i] = min(dp[i - 1], dp[i - 2], dp[i - 3] + max(k - i, 0)) = min(1,1,2+1) = 1 但这里的应该结果是3
尝试修正1
多加一维dp[i][j] 表达当前当前i 被包进范围所需的最小修改j = 0表示没有修改本身，j = 1表示修改了自己, 那我们得到了新式子
dp[i][0] = min(dp[i - 1][1], dp[i - 2][1])自己不需要修改的前提下是前面两个有一个修改过 或者自己本身就不需要修改(即>= k) 即if (i >= k) dp[i][0] = min(dp[i][0], dp[i-3][1])dp[i][1] = dp[i - 3][1] + max(k - i, 0)如果我们改自己我们就不会在乎前面两个到底需不需要改了，因为我们自己就可以保证前面两个
当然也不对哈哈(想死)
对于样例[4,0,10,2,10,6] k = 8来说我们的二维dp = {{2147483647, 4}, {4, 8}, {4, 0}, {0, 10}, {0, 8}, {8, 2}} 在最后一步上 明明前面两个10都保证了，但是最后6还是会选给自己加2 这是因为我们比较前面两个值时只看了需要修改的值，而10 >= 8保证了10不需要修改