fork download 
  1. public class Main {
  2.     public static int paintFence(int n, int k) {
  3.         final int MOD = 1000000007;
  4.  
  5.         if (n == 0) return 0;
  6.         if (n == 1) return k;
  7.         if (n == 2) return (k * k) % MOD;
  8.         if (n == 3) return (int)(((long)k * k * k) % MOD);
  9.  
  10.         long[] dp1 = new long[n + 1];
  11.         long[] dp2 = new long[n + 1];
  12.         long[] dp3 = new long[n + 1];
  13.         long[] total = new long[n + 1];
  14.  
  15.         dp1[1] = k;
  16.         dp2[1] = 0;
  17.         dp3[1] = 0;
  18.         total[1] = dp1[1];
  19.  
  20.         dp1[2] = (long)k * (k - 1) % MOD;
  21.         dp2[2] = k;
  22.         dp3[2] = 0;
  23.         total[2] = (dp1[2] + dp2[2]) % MOD;
  24.  
  25.         dp1[3] = ((dp1[2] + dp2[2] + dp3[2]) * (k - 1)) % MOD;
  26.         dp2[3] = dp1[2];
  27.         dp3[3] = dp2[2];
  28.         total[3] = (dp1[3] + dp2[3] + dp3[3]) % MOD;
  29.  
  30.         for (int i = 4; i <= n; i++) {
  31.             dp1[i] = (total[i - 1] * (k - 1)) % MOD;
  32.             dp2[i] = dp1[i - 1];
  33.             dp3[i] = dp2[i - 1];
  34.             total[i] = (dp1[i] + dp2[i] + dp3[i]) % MOD;
  35.         }
  36.  
  37.         return (int) total[n];
  38.     }
  39.  
  40.     public static void main(String[] args) {
  41.         int n = 5, k = 2;
  42.         System.out.println("Total ways to paint the fence: " + paintFence(n, k));
  43.     }
  44. }
  45.  
  46. // Time Complexity: O(n)
  47. // Space Complexity: O(n)
Success #stdin #stdout 0.13s 53572KB
comments (?)
stdin 
Standard input is empty
stdout 
Total ways to paint the fence: 26
https://ideone.com/FjBn60
language:
Java (HotSpot 12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!