杭电计算机考研复试，数据结构面试问题总结

杭电计算机考研复试，软件工程面试总结

题目WA Jiana在ACM队的代号是188(kg)。188很喜欢边吃边捣鼓各种小游戏。近两天，她听说软工班的短学期在做贪吃蛇小游戏，这让贪吃的她很心动。她也很想做一个这样的小游戏，但是贪吃蛇实在是太高端了她不会写，于是她挑了一个更简单的游戏——数独。数独的游戏规则如下：用19内的数字填充一个9×9的矩阵，要求填充完后每行都恰好用到19中的每个一个数字（位置不限），每列也恰好用到19中的每个数字（

前提概要首先呢，滚动数组是一种能够在动态规划中降低空间复杂度的方法，有时某些二维dp方程可以直接降阶到一维，在某些题目中甚至可以降低时间复杂度，是一种极为巧妙的思想，简要来说就是通过观察dp方程来判断需要使用哪些数据，可以抛弃哪些数据，一旦找到关系，就可以用新的数据不断覆盖旧的数据量来减少空间的使用，接下来我会介绍一些有关滚动数组的一些题目。以斐波那契数列为例我们先以斐波那契数列来简单感受一下滚动