鱼C论坛

 找回密码
 立即注册
查看: 2051|回复: 4

[技术交流] C++刷LeetCode(1411. 给 N x 3 网格图涂色的方案数)【动态规划】

[复制链接]
发表于 2020-6-26 11:43:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2020-6-26 11:45 编辑

题目描述:
  1. 你有一个 n x 3 的网格图 grid ,你需要用 红,黄,绿 三种颜色之一给每一个格子上色,且确保相邻格子颜色不同(也就是有相同水平边或者垂直边的格子颜色不同)。

  2. 给你网格图的行数 n 。

  3. 请你返回给 grid 涂色的方案数。由于答案可能会非常大,请你返回答案对 10^9 + 7 取余的结果。



  4. 示例 1:

  5. 输入:n = 1
  6. 输出:12
  7. 解释:总共有 12 种可行的方法:

  8. 示例 2:

  9. 输入:n = 2
  10. 输出:54
  11. 示例 3:

  12. 输入:n = 3
  13. 输出:246
  14. 示例 4:

  15. 输入:n = 7
  16. 输出:106494
  17. 示例 5:

  18. 输入:n = 5000
  19. 输出:30228214


  20. 提示:

  21. n == grid.length
  22. grid[i].length == 3
  23. 1 <= n <= 5000
复制代码

  1. class Solution {
  2. public:
  3.     int numOfWays(int n) {
  4.             int mode = 1e9+7;
  5.         if (n == 1) return 12;
  6.         vector<long> a{6};
  7.         vector<long> b{6};
  8.         for (int i = 1; i < n; i++) {
  9.             a.push_back((a[i - 1] * 3 + b[i - 1] * 2) % mode);
  10.             b.push_back((a[i - 1] * 2 + b[i - 1] * 2) % mode);
  11.         }
  12.         return (a.back() + b.back()) % mode;
  13.     }
  14. };
复制代码



参考链接:https://leetcode-cn.com/problems ... -gui-hua-by-klaxxi/

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2020-6-26 11:46:31 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2020-6-26 11:54:32 | 显示全部楼层
和你使用同样的方法,但减少了内存占用,提高了效率:
  1. class Solution {
  2. public:
  3.     int numOfWays(int n) {
  4.         const static int mod = 1000000007;
  5.         long temp, a = 6, b = 6;

  6.         while (--n) {
  7.             temp = a;
  8.             a = (temp * 3 + (b << 1)) % mod;
  9.             b = (temp + b << 1) % mod;
  10.         }

  11.         return (a + b) % mod;
  12.     }
  13. };
复制代码
少开数组总是好事。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2020-6-26 11:57:18 | 显示全部楼层
第一次发现……力扣的测试机上的 long 是 64 位的……
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-6-26 12:43:42 | 显示全部楼层
永恒的蓝色梦想 发表于 2020-6-26 11:54
和你使用同样的方法,但减少了内存占用,提高了效率:少开数组总是好事。

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-13 15:35

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表