山西企业网站模板建站平台,wordpress小白能学会吗,旅游网站建设的可行性分析,wordpress nginx配置有一个无穷大的二维网格图#xff0c;一开始所有格子都未染色。给你一个正整数 n #xff0c;表示你需要执行以下步骤 n 分钟#xff1a;第一分钟#xff0c;将任一格子染成蓝色。之后的每一分钟#xff0c;将与蓝色格子相邻的 所有 未染色格子染成蓝色。下图分别是 1、2、…有一个无穷大的二维网格图一开始所有格子都未染色。给你一个正整数 n 表示你需要执行以下步骤 n 分钟第一分钟将任一格子染成蓝色。之后的每一分钟将与蓝色格子相邻的 所有 未染色格子染成蓝色。下图分别是 1、2、3 分钟后的网格图。请你返回 n 分钟之后 被染色的格子 数目。题目链接https://leetcode.cn/problems/count-total-number-of-colored-cells今天刷到这题觉得有意思。在纸上画的麻烦搞个excel涂色还挺减压的就像这样n1时红色1n2时多了橙色1 4 5n3时多了绿色5 8 13n4时多了紫色13 12 25观察下规律来了n1时红色1 1 1 - 1* 4 n2时多了橙色1 4 5 1 2 - 1* 4 n3时多了绿色5 8 13 5 3 - 1* 4 n4时多了紫色13 12 25 13 4 - 1* 4那么公式就是: 后一个数 前一个数 n-1*4 这让人联想到类似斐波拉契数组的解法F(n) F(n-1) (n-1) * 4于是代码如下可见非常低效因为太多重复计算了。既然都知道公式了可以把公式用作 DP 动态规划转移方程可以将粗暴递归的重复计算变成线性的 O(n) 规模。于是代码如下有一点点提升发大招上数学归纳法这是我家女神帮我算的我这学渣不懂说是什么高斯定理高斯是谁大家知道吗什么字不好看风大听不见你再说一遍哦哦没关系人漂亮啊管他呢现在有了公式代码就只要一行了秀的简直不行不行的。感受下击败100%数学好就是秒杀全场什么迭代什么动态规划都不在话下。所以同学们弟弟妹妹们还是好好学数学吧。当然还有一个 excel 图像法我不会推公式我会画图小学数学老师教的 “加辅助线” 加辅助线也能推导出用高斯推导出来的那个啥公式你看看。四条红色的辅助线把图像分成了四个大红块加中间一个小红块中间一个小红块就是1大红块的规律看右下角标了数字好数。这是 n 4 时候的图长方形的面积等于长乘以宽4乘以3然后去掉灰色的恰好是一半4*3/2那么得到公式就是n-1乘以 n 乘积的一半。那么最终的公式就是F(n) 4 个大红块面积的一半 1 个小红块 两个大红块面积 1个小红块 2 * n *n-1 1所以图形化的学数学简直太棒了。这点建议希望数学老师参考下哈不然学得没有趣味还会有很多我这样的学渣
