[Javascript] Bitmask & DFS with Cache
Javascript version of - https://leetcode.com/problems/painting-a-grid-with-three-different-colors/discuss/1330185/C%2B%2BPython-DP-and-DFS-and-Bitmask-Picture-e
Javascript version of - https://leetcode.com/problems/painting-a-grid-with-three-different-colors/discuss/1330185/C%2B%2BPython-DP-and-DFS-and-Bitmask-Picture-explain-Clean-and-Concise\n\n```\n// To store previous column state in DP, we can use BitMask,\n// each 2 bits store a color (1=Red, 2=Green, 3=Blue, 0=White),\n// so there is total 4^M column states.\nvar colorTheGrid = function (m, n) {\n  // Generate all possible columns we can draw, if the previous col is \'prevColMask\'\n  const getNextState = (prevState) => {\n    // Get color of the \'state\' at \'pos\', use 2 bits to store a color\n    const getColor = (state, pos) => (state >> (2 * pos)) & 3;\n    // Set \'color\' to the \'state\' at \'pos\', use 2 bits to store a color\n    const setColor = (state, pos, color) => state | (color << (2 * pos));\n    const res = [];\n    const helper = (row, curState, prevState) => {\n      // Fill all color for this column\n      if (row === m) {\n        res.push(curState);\n        return;\n      }\n      // Try colors i in [1=RED, 2=GREEN, 3=BLUE]\n      for (let i = 1; i <= 3; i++) {\n        if (\n          getColor(prevState, row) !== i &&\n          (row === 0 || getColor(curState, row - 1) !== i)\n        )\n          helper(row + 1, setColor(curState, row, i), prevState);\n      }\n    };\n    helper(0, 0, prevState);\n    return res;\n  };\n\n  const dp = Array.from(Array(n), () => Array(4 ** m));\n\n  const dfs = (col = 0, prevState = 0) => {\n    if (col === n) return 1;\n    if (dp[col][prevState]) return dp[col][prevState];\n    let res = 0;\n    for (const nextState of getNextState(prevState)) {\n      res = (res + dfs(col + 1, nextState)) % (10 ** 9 + 7);\n    }\n    return (dp[col][prevState] = res);\n  };\n\n  return dfs();\n};\n```
[]