2024 年第 26 题阅读程序动态规划提高
程序(二):修改转移方程后的输出
题目
阅读下面的程序,回答问题。 #include <iostream> #include <vector> using namespace std; int compute(vector<int> &cost) { int n = cost.size(); vector<int> dp(n + 1, 0); dp[1] = cost[0]; for (int i = 2; i <= n; i++) { dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1]; } return min(dp[n], dp[n - 1]); } int main() { int n; cin >> n; vector<int> cost(n); for (int i = 0; i < n; i++) { cin >> cost[i]; } cout << compute(cost) << endl; return 0; } 若将代码中的 min(dp[i-1],dp[i-2])+cost[i-1] 修改为 dp[i-1]+cost[i-2],输入 cost 数组为{5,10,15}时,程序的输出为( )
考点拆解
动态规划
易错提醒
阅读程序题要按变量变化顺序手推,不要跳步
选择题要检查单位、边界和题目中的否定词