标签: 动态规划
难度: Medium
Submission
运行时间: 20 ms
内存: 0.0 MB
class Solution:
def numWays(self, n: int, k: int) -> int:
if n==0 or n==None: return 0
if n==1: return k
dp = [0] * (n+1)
dp[1] = k
same, diff = 0, k
for i in range(2,n+1):
same = diff
diff = dp[i-1]*(k-1)
dp[i] = same+diff
return dp[-1]
Explain
这是一个动态规划问题。dp[i] 表示涂完前 i 根栅栏的方案数。对于第 i 根栅栏，我们有两种选择： 1. 如果它和前一根栅栏颜色相同，则它的方案数等于前一根栅栏与前前一根栅栏颜色不同的方案数，即 same = diff。 2. 如果它和前一根栅栏颜色不同，则它的方案数等于前一根栅栏的方案数乘以 (k-1)，即 diff = dp[i-1] * (k-1)。 最终，第 i 根栅栏的方案数等于 same + diff。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def numWays(self, n: int, k: int) -> int:
if n == 0 or n is None: return 0 # 特殊情况处理
if n == 1: return k # 只有一根栅栏时的方案数
dp = [0] * (n+1) # 初始化动态规划数组
dp[1] = k # 第一根栅栏的方案数
same, diff = 0, k # 初始化相同和不同颜色的方案数
for i in range(2, n+1):
same = diff # 更新相同颜色的方案数
diff = dp[i-1] * (k-1) # 更新不同颜色的方案数
dp[i] = same + diff # 计算总方案数
return dp[-1] # 返回最后一个栅栏的方案数
Explore
在初始化阶段，`same`是指第二根栅栏和第一根栅栏颜色相同的方案数。由于只有一根栅栏存在时，不存在前一根与之比较的栅栏，因此`same`初始化为0是合理的，表示没有栅栏颜色相同的方案。`diff`代表第二根栅栏与第一根栅栏颜色不同的方案数，初始化为`k`意味着第一根栅栏有`k`种涂色方式，且每种方式都可以作为起始点。
在动态规划中，`same = diff`表示当前栅栏颜色与前一根相同的方案数（same）等于上一次计算中前一根栅栏与其前一根栅栏颜色不同的方案数（diff）。这是因为如果当前栅栏要与前一根颜色相同，则前一根栅栏必须与其前一根颜色不同，以避免与更前一根颜色连续相同。因此，将`diff`的值赋给`same`是为了在下一次循环中使用，这反映了这种依赖关系。
`diff = dp[i-1] * (k-1)`表示当前栅栏与前一根栅栏颜色不同的方案数。这里乘以`(k-1)`是因为如果当前栅栏颜色需要与前一根不同，那么可以选择的颜色数就是总颜色数`k`减去前一根栅栏的颜色1种，即`k-1`种。这种计算方式确实考虑了所有可能的颜色组合，因为它包括了每一种可以与前一根栅栏颜色不同的颜色选择。
当`n`为0时，意味着没有栅栏需要涂色，因此没有任何涂色的方案，返回0是合理的。这里返回0代表方案数为零，这是最合适的返回值，因为它正确地表示了不存在栅栏的情况下的涂色方案数。返回其他值，如1或者负数，会误导理解，因为涂色方案数应该反映实际可执行的操作数量。