Участник:Vovaf709/grid paint

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/

class Solution {
public:
  int numOfWays(int n) {
    constexpr int Mod = 1e9 + 7;
    vector<vector<long>> dp(n + 1, vector<long>(2, 6));        
    for (int i = 2; i <= n; ++i) {     
      dp[i][0] = (dp[i - 1][0] * 3 + dp[i - 1][1] * 2) % Mod;
      dp[i][1] = (dp[i - 1][0] * 2 + dp[i - 1][1] * 2) % Mod;
    }
    return (dp[n][0] + dp[n][1]) % Mod;
  }
};