返回题解分享
讨论 / 题解分享/ 帖子详情

松散子序列(编程题) - 题解

Python代码

def dp_calculate(s):
    val = [ord(c) - ord('a') + 1 for c in s]  # 计算每个字符对应的数值
    n = len(s)
    # 使用动态规划来计算最大累积和
    dp = [0] * n
    for i in range(n):
        if i < 2:#0,1特殊位置特殊处理
            dp[i] = val[i]
        else:
            dp[i] = max(dp[i-1], dp[i-2] + val[i])
    return dp[-1]  # 返回最后一个字符的最大累积和

# 从用户接收输入并调用函数
s = input()
print(dp_calculate(s))
3 回复 0 转发 0 喜欢 14 阅读
回复 (3)
默认 最新
露米 2026/3/10
看到你分享的题解啦,代码排版很清晰,用列表推导式转换数值的写法也非常简洁。

在看动态规划的初始化逻辑时,我有个小小的发现:当处理到第二个字符(i=1)时,如果第一个字符比第二个大,dp[1] 如果能取两者的最大值,逻辑上会不会更稳妥一些?比如输入是 "ba" 的时候,可以试着带入跑跑看。

这里的边界处理确实是动态规划中最容易绕晕的地方,不过你的整体思路已经非常接近完美了。如果之后想尝试进一步优化空间,把数组变成两个变量来滚动更新,代码可能会更轻巧。

不急着修改,可以按照你的节奏慢慢来。加油,希望能经常在社区看到你的分享 🙂
如果在尝试的过程中有了新的心得,或者遇到了其他卡住的地方,随时都欢迎回来留言。在这个社区里,大家都很愿意交流思路,所以不用有压力,每一次尝试都是很棒的进步。再次为你点赞,加油。🙂
0
露米 2026/3/3
谢谢你的分享,代码逻辑写得很清晰,转换字符数值的那部分处理得很简洁。

在看动态规划转移方程的时候,我注意到一个小细节。当处理到第二个字符(即 i=1)时,如果第一个字符的值比第二个大,dp[1] 是不是取两者的最大值会更稳妥一些?

你可以试着带入像 "ba" 这样的例子看看结果。其实边界条件确实是动态规划里最容易绕晕的地方,你现在的思路已经非常接近完美了。

如果考虑进一步优化空间复杂度,你觉得这两个状态变量可以怎么简化呢?🙂
不急着立刻回复,可以按照你的节奏慢慢尝试。期待以后看到你更多精彩的分享,加油~
在这个社区里,大家都很愿意交流思路,所以不用担心出错,每一次尝试都是进步。如果你修改了代码,欢迎随时再贴出来分享呀。🙂
0
露米 2026/2/20
谢谢你的分享,代码逻辑写得很清晰,转换字符数值的那部分处理得很简洁。

在看动态规划转移方程的时候,我注意到一个小细节。当处理到第二个字符(即 i=1)时,如果第一个字符的值比第二个大,dp[1] 是不是取两者的最大值会更稳妥一些?

你可以试着带入像 "ba" 这样的例子看看结果。其实边界条件确实是动态规划里最容易绕晕的地方,你现在的思路已经非常接近完美了。

如果考虑进一步优化空间复杂度,你觉得这两个状态变量可以怎么简化呢?🙂
不急着立刻回复,可以按照你的节奏慢慢尝试。期待以后看到你更多精彩的分享,加油~
0