Rust | Bottom-up DP, 6ms, beats 100%
Intuition\nCompress each row into vertices, construct a graph and do DP on it.\n\n# Complexity\n- Time complexity:\nO(n)\n\n# Code\nrust\n#[derive(Debug, Clone,
# Intuition\nCompress each row into vertices, construct a graph and do DP on it.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n# Code\n```rust\n#[derive(Debug, Clone, PartialOrd, Ord, PartialEq, Eq)]\npub enum Color {\n    Blue,\n    Pink,\n    White,\n}\n\npub fn to_vertices(\n    width: usize,\n) -> Vec<Vec<Color>> {\n    fn backtrack(\n        width: usize,\n        parent_vec: &mut Vec<Color>,\n        ret: &mut Vec<Vec<Color>>,\n    ) {\n        if parent_vec.len() >= width {\n            return ret.push(parent_vec.clone());\n        }\n\n        for color_next in [\n            Color::Blue, Color::Pink, Color::White,\n        ] {\n            if Some(&color_next) == parent_vec.last() {\n                continue;\n            }\n\n            // BEGIN backtracking\n            parent_vec.push(color_next);\n            backtrack(width, parent_vec, ret);\n            parent_vec.pop();\n            // END backtracking\n        }\n    }\n\n    let mut ret = vec![];\n    backtrack(\n        width,\n        &mut Vec::with_capacity(width),\n        &mut ret,\n    );\n\n    ret\n}\n\npub fn to_graph(\n    vertices: Vec<Vec<Color>>,\n) -> Vec<Vec<usize>> {\n    let n = vertices.len();\n\n    let mut ret = vec![vec![]; n];\n    \n    for i in 0..n {\n        for j in 0..n {\n            let v = vertices[i].clone();\n            let v_next = vertices[j].clone();\n            if v.into_iter().zip(v_next.into_iter())\n                .any(|(e0, e1)| e0 == e1) {\n                continue;\n            }\n\n            ret[i].push(j);\n        }\n    }\n\n    ret\n}\n\nconst MOD: usize = 1_000_000_007;\n\nimpl Solution {\n    pub fn color_the_grid(m: i32, n: i32) -> i32 {\n        let (m, n) = (m as usize, n as usize);\n        let vertices = to_vertices(m);\n        let dp_width = vertices.len();\n        let graph = to_graph(vertices);\n\n        let mut dp = vec![1usize; dp_width];\n        for _ in 1..n {\n            let mut dp_next = vec![usize::MIN; dp_width];\n\n            for (v, count) in dp.into_iter().enumerate() {\n                for &v_next in &graph[v] {\n                    dp_next[v_next] += count;\n                }\n            }\n            for e in &mut dp_next { *e %= MOD; }\n\n            dp = dp_next;\n        }\n\n        let mut ret = dp.into_iter().sum::<usize>();\n        ret %= MOD;\n\n        ret as i32\n    }\n}\n```
['Dynamic Programming', 'Rust']