Leetcode每日一题：锯齿形数组的总数I解题思路与代码实现

Leetcode每日一题 —— 3699. 锯齿形数组的总数 I

题目描述：
给定三个整数n、l和r。长度为n的锯齿形数组定义如下：

• 每个元素的取值范围为 [l, r]。
• 任意两个相邻的元素都不相等。
• 任意三个连续的元素不能构成一个严格递增或严格递减的序列。

返回满足条件的锯齿形数组的总数。

解题思路：
为了生成满足条件的锯齿形数组，我们可以使用动态规划的方法。定义dpi表示长度为i且以数字j结尾的锯齿形数组的数量。状态转移方程可以表示为：

dpi = dpi-1 - dpi-2，其中k是除了j之外的其他数字，且满足l <= k <= r。

初始条件为dp1 = 1，因为长度为1的数组只有一种情况，即数组本身。

最终的结果是所有dpn的和，其中j为l到r之间的任意数字。

代码实现：

def count锯齿形数组(n, l, r):
    dp = [[0] * (r - l + 1) for _ in range(n + 1)]
    for j in range(l, r + 1):
        dp[1][j - l] = 1
    for i in range(2, n + 1):
        for j in range(l, r + 1):
            for k in range(l, r + 1):
                if k != j:
                    dp[i][j - l] += dp[i - 1][k - l] - dp[i - 2][k - l]
    return sum(dp[n])

# 示例
n = 3
l = 1
r = 3
result = count锯齿形数组(n, l, r)
print(result)

以上代码实现了计算长度为n，元素取值范围为[l, r]的锯齿形数组的总数。通过动态规划的方法，我们可以有效地解决这个问题。希望这个解答对您有所帮助。