1 刷油漆問(wèn)題

給定一個(gè)有n根柱子和k種顏色的圍欄，找出油漆圍欄的方法，使最多兩個(gè)相鄰的柱子具有相同的顏色。因?yàn)榇鸢缚梢允谴蟮?#xff0c;所以返回10^9+7的模。

計(jì)算結(jié)果：

2 柵欄油漆算法的源程序

using System;

namespace Legalsoft.Truffer.Algorithm
{
?? ?public static partial class Number_Sequence
?? ?{
?? ??? ?public static long Painting_Fence_Number(int n, int k)
?? ??? ?{
?? ??? ??? ?long[] dp = new long[n + 1];
?? ??? ??? ?int mod = 1000000007;
?? ??? ??? ?dp[1] = k;

?? ??? ??? ?int same = 0;
?? ??? ??? ?int diff = k;

?? ??? ??? ?for (int i = 2; i <= n; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?same = diff;

?? ??? ??? ??? ?diff = (int)(dp[i - 1] * (k - 1));
?? ??? ??? ??? ?diff = diff % mod;

?? ??? ??? ??? ?dp[i] = (same + diff) % mod;
?? ??? ??? ?}

?? ??? ??? ?return dp[n];
?? ??? ?}

?? ??? ?public static long Painting_Fence_Number_Second(int n, int k)
?? ??? ?{
?? ??? ??? ?long total = k;
?? ??? ??? ?int mod = 1000000007;

?? ??? ??? ?long same = 0;
?? ??? ??? ?long diff = k;

?? ??? ??? ?for (int i = 2; i <= n; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?same = diff;

?? ??? ??? ??? ?diff = total * (k - 1);
?? ??? ??? ??? ?diff = diff % mod;

?? ??? ??? ??? ?total = (same + diff) % mod;
?? ??? ??? ?}

?? ??? ??? ?return total;
?? ??? ?}
?? ?}
}
?

——————————————————

POWER BY TRUFFER.CN

3 代碼格式

using System;namespace Legalsoft.Truffer.Algorithm
{public static partial class Number_Sequence{public static long Painting_Fence_Number(int n, int k){long[] dp = new long[n + 1];int mod = 1000000007;dp[1] = k;int same = 0;int diff = k;for (int i = 2; i <= n; i++){same = diff;diff = (int)(dp[i - 1] * (k - 1));diff = diff % mod;dp[i] = (same + diff) % mod;}return dp[n];}public static long Painting_Fence_Number_Second(int n, int k){long total = k;int mod = 1000000007;long same = 0;long diff = k;for (int i = 2; i <= n; i++){same = diff;diff = total * (k - 1);diff = diff % mod;total = (same + diff) % mod;}return total;}}
}