一、单项选择题（每题2分，共20分）

1、动态规划当中，把大问题拆解成若干小问题，保存子问题解避免重复计算，这个特性叫做？（） {{ select(1) }}

• 无后效性
• 重叠子问题
• 最优子结构
• 贪心策略

2、下面不属于动态规划三要素的是？（） {{ select(2) }}

• 最优子结构
• 无后效性
• 递归回溯
• 重叠子问题

3、台阶走法，一次走1阶或者2阶，到达第n阶的状态转移方程是？（） {{ select(3) }}

• dp[n]=dp[n‑1]+dp[n‑2]
• dp[n]=dp[n‑1]*2
• dp[n]=dp[n‑2]+2
• dp[n]=n

4、网格只能向右、向下行走，dp[i][j]代表走到(i,j)的方案数，状态转移方程正确的是？（） {{ select(4) }}

• dp[i][j] = dp[i‑1][j] - dp[i][j‑1]
• dp[i][j] = dp[i‑1][j] * dp[i][j‑1]
• dp[i][j] = dp[i‑1][j]
• dp[i][j] = dp[i‑1][j] + dp[i][j‑1]

5、挖矿（花生地）题目，只能向右向下，求路径最大和，dp[i][j]代表到达该格子最大矿石数，转移方程为？（） {{ select(5) }}

• dp[i][j] = min(dp[i‑1][j], dp[i][j‑1]) + mp[i][j]
• dp[i][j] = max(dp[i‑1][j], dp[i][j‑1]) + mp[i][j]
• dp[i][j] = dp[i‑1][j] + dp[i][j‑1]
• dp[i][j] = max(dp[i‑1][j], dp[i][j‑1])

6、硬币问题，dp[i]表示凑i元需要最少硬币数，dp[i]正确写法是？（） {{ select(6) }}

• dp[i] = max(dp[i], dp[i‑coin]+1)
• dp[i] = dp[i‑coin]
• dp[i] = min(dp[i], dp[i‑coin]+1)
• dp[i] = dp[i‑coin]‑1

7、硬币问题初始化，dp[0]应当赋值为？（） {{ select(7) }}

• 极大值
• 0
• 1
• -1

8、关于无后效性，下面描述正确的是？（） {{ select(8) }}

• 当前状态求解，需要用到全部历史所有状态
• 子问题会被重复多次调用
• 子问题的最优解构成全局最优解
• 当前状态只依赖上一步状态，更早的状态不再需要

9、memset函数对于int数组，下面说法正确的是？（） {{ select(9) }}

• memset可以直接把int数组赋值为1000000
• memset按字节赋值，不适合直接给int赋大数值
• memset只能用于char数组
• memset可以用来求状态转移方程

10、方格取数CSP‑J题，数组f[i][j][0]的含义是？（） {{ select(10) }}

• 到达(i,j)，向下走的累加最大值
• 到达(i,j)，向上走的累加最大值
• (i,j)格子原始数值
• 该点访问标记

二、判断题（每题2分，共10分）

11、动态规划求解步骤：确定状态转移方程、初始化状态、执行状态转移。（） {{ select(11) }}

• 正确
• 错误

12、最优子结构含义：大问题的最优解由各个子问题最优解构成。（） {{ select(12) }}

• 正确
• 错误

13、挖矿花生地，dp数组第0行第0列需要初始化为极大负数。（） {{ select(13) }}

• 正确
• 错误

14、硬币问题，dp数组整体初始要设置为极大值，dp[0]=0。（） {{ select(14) }}

• 正确
• 错误

15、下棋博弈问题具备无后效性，可以直接使用动态规划求解。（） {{ select(15) }}

• 正确
• 错误