青蛙跳荷叶问题
题目如图。 本帖最后由 aimisiyou 于 2020-11-3 12:13 编辑之前所在QQ某算法群里，别人都说可用DP解决，但没见着具体的DP内容。我根据构造法可以得到一个函数结果，但无法证明是否就是最优结果（验算了几个小数据，都正确），其实就是想提出来看别人能否给出反例（群里我没说结果一定正确），来检验我的结果是否正确。结果被QQ群主痛批为“一看就是民科，异想天开。答案怎么可能这么简单。”。我也是一脸懵*，一个算法问题，根据构造法列了个“通项公式“，就被提升到“民科“（这又不是世界难题猜想）。跟群主争论了两句（我一直冷静克制），如预期中结果，被踢出群了。
也好，云淡风轻。 本帖最后由 aimisiyou 于 2020-11-3 12:49 编辑
仔细想了下，其实就是一笔画问题，即删掉最少的边数，使其构成一笔画图形。 本帖最后由 markfang2050 于 2020-11-5 09:17 编辑
# -*- coding: utf-8 -*-
#python 3.8
"""
Created on Wed Nov4 21:12:02 2020
One is Never too old to learn.
@author: NicholasTU
"""
def foo(n,ar):
"""
动态规划解青蛙跳荷叶
m_l 为状态映射：l->n
l为某一状态，状态标识方式为l为当前青蛙位置，取1-n，
l为荷叶间剩余跳跃次数
n为该状态下青蛙最多跳几次
"""
m_l = dict()
def find(l):
nonlocal m_l
if l not in m_l:
#青蛙位于左边界情况
if l == 1:
if l] == 0:
#无路可走，状态映射为0
m_l =0
else:
#右跳一步作为下一状态，当前状态映射为下一状态步数+1
l2 = list(l)
l2 -=1
l2 = tuple(+l2)
m_l = find(l2)+1
#青蛙位于右边界情况
elif l == n:
if l ==0:
#无路可走，状态映射为0
m_l =0
else:
#左跳一步作为下一状态，当前状态映射为下一状态步数+1
l2 = list(l)
l2 -=1
l2 = tuple(+l2)
m_l = find(l2)+1
#青蛙位于中间状态
else:
if l] == 0 and l-1] == 0:
#无路可走，状态映射为0
m_l = 0
elif l-1] == 0:
#右侧无路，左跳一步作为下一状态，当前状态映射为下一状态步数+1
l3 = list(l)
l3-1] -= 1
l3 = tuple(+1,]+l3)
m_l = find(l3)+1
elif l] == 0:
#左侧无路，右跳一步作为下一状态，当前状态映射为下一状态步数+1
l2 = list(l)
l2 - 2] -= 1
l2 = tuple(-1,]+l2)
m_l = find(l2) +1
else:
#左右各跳一部作为下一状态，当前状态映射为下一状态步数较大一状态值+1
l2 = list(l)
l2 - 2] -= 1
l2 = tuple(-1,]+l2)
l3 = list(l)
l3-1] -= 1
l3 = tuple(+1,]+l3)
m_l = max(find(l2),find(l3))+1
return m_l
ans = list()
for i in range(n):
ans.append(find(tuple(+list(ar))))
return max(ans)
print(foo(10,(2,18,2,8,2,6,2,5,7)))
====================================
输出：52
提示:从第10片叶子出发按(10, 9, 10, 9, 10, 9, 10, 9, 8, 9, 8, 9, 8, 7, 6, 7, 6, 7, 6, 5, 4, 5, 4, 5, 4, 5, 4, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 1, 2, 3, 4, 5, 6, 7, 8)的次序跳跃。 动态规划——将需要重复计算的问题保存起来，不需要下次重新计算。对于斐波那契数列，算法复杂度为O（n）。
递归调用是非常耗费内存的，程序虽然简洁可是算法复杂度为O(2^n)，当n很大时，程序运行很慢，甚至内存爆满。
DP算法思想
（1）将待求解的问题分解称若干个子问题，并存储子问题的解而避免计算重复的子问题，并由子问题的解得到原问题的解。
（2）动态规划算法通常用于求解具有某种最有性质的问题。
（3）动态规划算法的基本要素：最优子结构性质和重叠子问题。 科学和迷信的分界点是哪里？
答：是否承认：“我错了”。 markfang2050 发表于 2020-11-4 21:26
# -*- coding: utf-8 -*-
#python 3.8
"""
嗯，是的，这是个反例。按一笔画思路相邻数目相加（除首尾保持不变外）依次得到每个点的“度数”即（2,20,20，10,10,8,8,7,12,7），只有两个点的度数为奇数，故可以组成一笔画，即总跳跃次数为原各项最大跳跃次数之和，故为52. 本帖最后由 aimisiyou 于 2020-11-6 11:22 编辑
markfang2050 发表于 2020-11-4 21:37
动态规划——将需要重复计算的问题保存起来，不需要下次重新计算。对于斐波那契数列，算法复杂度为O（n）。 ...
只是觉得DP有时很难找出状态转移关系式，只是尝试别的思路来轻松解题。当然我那个式子是根据构造法来构造一个可行的跳跃过程，但次数确实不是最多的。（忽略了你所给出的数据这种情形）
页:
[1]