K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
动态规划是算法设计中用于解决存在重叠子问题、最优子结构特性问题的常用方法，本题考查动态规划基础实现的核心概念与规则。
动态规划求解问题时，必须按照从大到小的顺序计算子问题的解
如果一个问题可以用递归求解，就一定可以用动态规划优化时间复杂度
用C++实现基础01背包问题的动态规划解法时，状态转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])中，dp[i][j]表示前i个物品放入容量为j的背包能获得的最大价值
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
dp[i][j]
动态规划的空间复杂度一定高于暴力递归解法