【入门dp】力扣鸡蛋掉落问题和转账问题的关系初探
本帖最后由 hans7 于 2023-7-16 13:02 编辑## 题目
我昨晚偶然编出了一道水题，名为转账问题：已知银行卡里有不超过`n`元，你想把卡里所有钱提到某信支付，但你无法看到卡里的钱，你只能执行若干次转账`i`元的操作，每次看到转账成功与失败的提示。问至少需要操作多少次。`n`和`i`是自然数。形式化描述：你的策略`y`是一段代码，初始输入为`n`，代码对于实际的`i = 1~n`元各有一个需要的猜测次数`x`，则`y = max(x for i in range(1, n + 1))`，所求为`min(y for y in y_set)`。
本文CSDN：https://blog.csdn.net/hans774882968/article/details/131749241
本文juejin：https://juejin.cn/post/7255967761805197349
本文52pojie：https://www.52pojie.cn/thread-1809085-1-1.html
**作者：(https://blog.csdn.net/hans774882968)以及(https://juejin.cn/user/1464964842528888)以及(https://www.52pojie.cn/home.php?mod=space&uid=1906177)**
## 思路
尝试转`i`元，`1 <= i <= n`。如果成功，则知道卡里不超过`n - i`元；如果失败，则知道卡里不超过`i - 1`元。因此定义`dp`为已知银行卡里有不超过`i`元时的最少操作次数。边界条件：`dp = 0~2`。状态转移方程：`dp = min(max(dp, dp) + 1) for j in range(1, i + 1)`。
接下来考虑优化这个dp转移。有一个很明显的单调性：`v1 < v2`时`dp <= dp`。`i - j`单减，`j - 1`单增，因此取`i - j == j - 1`的`j`即为最优点。
- 若`i`为奇数，则dp下标取到`(i - 1) // 2`。
- 若`i`为偶数，则dp下标取到`(i - 1) // 2 + 1`。
取到下标可统一为`i // 2`。因此转移方程可以简化为：`dp = dp + 1`。对于`n`，答案居然就是`n`二进制数位的个数！
于是有推论：最优策略为：总是尝试转`i - i // 2 = (i + 1) // 2`元。
### 与力扣鸡蛋掉落问题的关系
[鸡蛋掉落问题传送门](https://leetcode.cn/problems/super-egg-drop/)
经群友提醒，这个问题从状态转移方程的角度来看，和鸡蛋掉落问题的`k = +∞`的情况类似。两个问题从题面来看不像，但它们有一个相同点：1次操作无论获得什么反馈，都能缩小问题规模。因此我们写了下面的代码，验证`k = n, n+1, n+2`的情况下所得的dp数组不仅相等，还等于转账问题的dp数组。
### 代码
```python
import numpy as np
def main():
N = 2001
dp1 = [ * N for _ in range(N + 2)]
def egg_drop(k, n):
for j in range(1, n + 1):
dp1 = j
for i in range(2, k + 1):
best = 1
for j in range(1, n + 1):
while best <= j and dp1 > dp1:
best += 1
dp1 = 1 + min(dp1, dp1)
dp2 = np.array( * N)
def bin_count(n):
for i in range(1, n + 1):
dp2 = dp2 + 1
dp3 = np.array( * N)
def n2_dp(n):
dp3 = 0
for i in range(1, n + 1):
for j in range(1, i + 1):
dp3 = min(dp3, max(dp3, dp3) + 1)
egg_drop(N + 1, N - 1)
bin_count(N - 1)
n2_dp(N - 1)
ans1 = np.array( for i in range(N)])
ans2 = np.array( for i in range(N)])
ans3 = np.array( for i in range(N)])
assert (ans1 == dp2).all() and (ans2 == dp2).all() and (ans3 == dp2).all() and (dp2 == dp3).all()
print('dp2 ', dp2[:101])
print('dp3 ', dp3[:101])
print('ans3', ans3[:101])
if __name__ == '__main__':
main()
``` 本帖最后由 hanghaidongchen 于 2023-7-16 17:46 编辑
有点没看懂那个转帐问题 hanghaidongchen 发表于 2023-7-16 17:44
有点没看懂那个转帐问题
可以先去看懂鸡蛋掉落问题，力扣里好的题解很多。看懂鸡蛋掉落问题后，我这个转账问题就秒懂了{:1_889:}
页:
[1]