classSolution{public:intnumWays(intn,intk){if(n==0)return0;if(n==1)returnk;if(n==2)returnk*k;// dp[i] := # of ways to paint n posts with k colorsvector<int>dp(n+1);dp[0]=0;dp[1]=k;dp[2]=k*k;for(inti=3;i<=n;++i)dp[i]=(dp[i-1]+dp[i-2])*(k-1);returndp[n];}};
classSolution{publicintnumWays(intn,intk){if(n==0)return0;if(n==1)returnk;if(n==2)returnk*k;// dp[i] := # of ways to paint n posts with k colorsint[]dp=newint[n+1];dp[0]=0;dp[1]=k;dp[2]=k*k;for(inti=3;i<=n;++i)dp[i]=(dp[i-1]+dp[i-2])*(k-1);returndp[n];}}
classSolution:defnumWays(self,n:int,k:int)->int:ifn==0:return0ifn==1:returnkifn==2:returnk*k# dp[i] := # Of ways to pan posts with k colorsdp=[0]*(n+1)dp[0]=0dp[1]=kdp[2]=k*kforiinrange(3,n+1):dp[i]=(dp[i-1]+dp[i-2])*(k-1)returndp[n]