Pyramid Transition Matrix Leetcode 756

题目

见pyramid transition matrix.
反正就是给几个允许的pattern ，看能不能凑成想要的态。
码不是自己的，来自wyh9346.

思路

还是妹的DP，DP好难啊
以bottom为准，穷举出下一层的所有可能。
注意allowed是准许的pattern意味着可以用无数次。
最后看能不能到达第n-1层

表格

代码

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>

using namespace std;
class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        int n = bottom.size();
        unordered_map<string, vector<char>> mp;
        vector<vector<set<char>>> dp(n, vector<set<char>>(n));

        for(string temp: allowed){
            mp[temp.substr(0,2)].push_back(temp[2]);
        }

        for(int i = 0; i < n ; ++i) {
            dp[0][i].insert(bottom[i]);
        }

        for(int i = 1; i < n; ++i){
            for(int j = 0; j < n-i; ++j){
                for(char a: dp[i-1][j]){
                    for(char b: dp[i-1][j+1]){
                        string s = "";
                        s = s+a+b;
                        for(char c: mp[s]){
                            dp[i][j].insert(c);
                        }
                    }
                }
            }
        }

        return !dp[n-1][0].empty();
    }
};

int main() {
    Solution s;
    string bottom = "XXYX";
    vector<string> allowed = {"XXX", "XXY", "XYX", "XYY", "YXZ"};

    cout << s.pyramidTransition(bottom,allowed) <<endl;

    return 0;
}

吐槽SF传图好慢啊！