蓝桥杯 分类

N = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
dp = [[0]*4 for _ in range(N+1)]
"""
dp[i][0] 代表 第i天元神 第i-1天元神
dp[i][1] 代表 第i天元神 第i-1天明日
dp[i][2] 代表 第i天明日 第i-1天元神
dp[i][3] 代表 第i天明日 第i-1天明日
"""
for i in range(1, N+1):
    dp[i][0] = dp[i-1][1] + a[i]
    dp[i][1] = max(dp[i-1][2], dp[i-1][3]) + a[i]
    dp[i][2] = dp[i-1][1] + b[i]
    dp[i][3] = max(dp[i-1][2], dp[i-1][3]) + b[i]

print(max(dp[N]))

'''
dp[i][0] 表示没有进行翻转时1的最大数量,只能由dp[i-1][0]推导出来
dp[i][1] 表示当前位正在进行翻转,所以前一位可以翻转也可以不翻转;
故dp[i][1] = max(dp[i-1][0],dp[i-1][1]) + 当前位的数的翻转结果
dp[i][2] 表示到当前位已经翻转结束,所以前一位可能正在翻转或者已经翻转结束
但i==1时,不可能翻转结束。
'''
l = int(input())
s = [0] + list(map(int, input()[:]))
dp = [[0 for _ in range(3)] for _ in range(l+1)]
for i in range(1, l+1):
    dp[i][0] = dp[i-1][0] + s[i]
    dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + (1-s[i])
    if i > 1:
        dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + s[i]

print(max(dp[l][0], dp[l][1], dp[l][2]))

题目的意思是向左走和向右走的结果的差值不能超过 1 过程中超过 1 是没有问题的

DFS 版本

这个版本会超时

n = int(input())
grid = [[0] * n] * n
for i in range(n):
    grid[i] = list(map(int, input().strip().split()))
ret = 0
def dfs(x, y, max_val, balance_factor):
    """
    :param x: 当前位置的横坐标
    :param y: 当前位置的纵坐标
    :param max_val: 上一层的最大值
    :param balance_factor: 左转减去右转的次数
    :return:
    """
    if y > x:
        return
    global ret
    if x == n - 1:  # 到达最后一列
        if abs(balance_factor) <= 1:
            ret = max(ret, max_val)
        return
    dfs(x + 1, y, max_val + grid[x + 1][y], balance_factor + 1)
    dfs(x + 1, y + 1, max_val + grid[x + 1][y + 1], balance_factor - 1)

dfs(0, 0, grid[0][0], 0)
print(ret)

在明日玩元神

翻转后1的数量

[蓝桥杯]Python 数字三角形 DFS or 动态规划

DFS 版本