青蛙跳荷叶问题

aimisiyou

题目如图。

aimisiyou

之前所在QQ某算法群里，别人都说可用DP解决，但没见着具体的DP内容。我根据构造法可以得到一个函数结果，但无法证明是否就是最优结果（验算了几个小数据，都正确），其实就是想提出来看别人能否给出反例（群里我没说结果一定正确），来检验我的结果是否正确。结果被QQ群主痛批为“一看就是民科，异想天开。答案怎么可能这么简单。”。我也是一脸懵*，一个算法问题，根据构造法列了个“通项公式“，就被提升到“民科“（这又不是世界难题猜想）。跟群主争论了两句（我一直冷静克制），如预期中结果，被踢出群了。
也好，云淡风轻。

aimisiyou

仔细想了下，其实就是一笔画问题，即删掉最少的边数，使其构成一笔画图形。

markfang2050

# -*- coding: utf-8 -*-
#python 3.8
"""
Created on Wed Nov  4 21:12:02 2020
One is Never too old to learn.
@author: NicholasTU
"""

def foo(n,ar):
   
    """
    动态规划解青蛙跳荷叶
    m_l 为状态映射：l->n
    l为某一状态，状态标识方式为l[0]为当前青蛙位置，取1-n，
    l[1:]为荷叶间剩余跳跃次数
    n为该状态下青蛙最多跳几次
    """
    m_l = dict()
    def find(l):
        nonlocal m_l
        if l not in m_l:
            #青蛙位于左边界情况
            if l[0] == 1:
                if l[l[0]] == 0:
                    #无路可走，状态映射为0
                    m_l[l] =0
                else:
                    #右跳一步作为下一状态，当前状态映射为下一状态步数+1
                    l2 = list(l[1:])
                    l2[0] -=1
                    l2 = tuple([2]+l2)
                    m_l[l] = find(l2)+1
            #青蛙位于右边界情况
            elif l[0] == n:
                if l[n-1] ==0:
                    #无路可走，状态映射为0
                    m_l[l] =0
                else:
                    #左跳一步作为下一状态，当前状态映射为下一状态步数+1
                    l2 = list(l[1:])
                    l2[n-2] -=1
                    l2 = tuple([n-1]+l2)
                    m_l[l] = find(l2)+1
            #青蛙位于中间状态
            else:
                if l[l[0]] == 0 and l[l[0]-1] == 0:
                    #无路可走，状态映射为0
                    m_l[l] = 0
                elif l[l[0]-1] == 0:
                    #右侧无路，左跳一步作为下一状态，当前状态映射为下一状态步数+1
                    l3 = list(l[1:])
                    l3[l[0]-1] -= 1
                    l3 = tuple([l[0]+1,]+l3)
                    m_l[l] = find(l3)+1
                elif l[l[0]] == 0:
                    #左侧无路，右跳一步作为下一状态，当前状态映射为下一状态步数+1
                    l2 = list(l[1:])
                    l2[l[0] - 2] -= 1
                    l2 = tuple([l[0]-1,]+l2)
                    m_l[l] = find(l2) +1
                else:
                    #左右各跳一部作为下一状态，当前状态映射为下一状态步数较大一状态值+1
                    l2 = list(l[1:])
                    l2[l[0] - 2] -= 1
                    l2 = tuple([l[0]-1,]+l2)
                    l3 = list(l[1:])
                    l3[l[0]-1] -= 1
                    l3 = tuple([l[0]+1,]+l3)
                    m_l[l] = max(find(l2),find(l3))+1
        return m_l[l]
    ans = list()
    for i in range(n):
        ans.append(find(tuple([i+1]+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)的次序跳跃。

markfang2050

动态规划——将需要重复计算的问题保存起来，不需要下次重新计算。对于斐波那契数列，算法复杂度为O（n）。
递归调用是非常耗费内存的，程序虽然简洁可是算法复杂度为O(2^n)，当n很大时，程序运行很慢，甚至内存爆满。

DP算法思想

　　（1）将待求解的问题分解称若干个子问题，并存储子问题的解而避免计算重复的子问题，并由子问题的解得到原问题的解。

　　 （2）动态规划算法通常用于求解具有某种最有性质的问题。

　　 （3）动态规划算法的基本要素：最优子结构性质和重叠子问题。

markfang2050

科学和迷信的分界点是哪里？
答：是否承认：“我错了”。

aimisiyou

markfang2050 发表于 2020-11-4 21:26
# -*- coding: utf-8 -*-
#python 3.8
"""

嗯，是的，这是个反例。按一笔画思路相邻数目相加（除首尾保持不变外）依次得到每个点的“度数”即（2,20,20，10,10,8,8,7,12,7），只有两个点的度数为奇数，故可以组成一笔画，即总跳跃次数为原各项最大跳跃次数之和，故为52.

aimisiyou

markfang2050 发表于 2020-11-4 21:37
动态规划——将需要重复计算的问题保存起来，不需要下次重新计算。对于斐波那契数列，算法复杂度为O（n）。 ...

只是觉得DP有时很难找出状态转移关系式，只是尝试别的思路来轻松解题。当然我那个式子是根据构造法来构造一个可行的跳跃过程，但次数确实不是最多的。（忽略了你所给出的数据这种情形）