解释动态规划（Dynamic Programming）的概念，并给出一个非斐波那契的例子。

Explain dynamic programming and give a non-Fibonacci example.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

分类: Algorithms

标签: DP, Knapsack, Optimal Substructure

参考答案摘要

答案 动态规划用于解决“最优子结构 + 重叠子问题”的问题：把大问题拆成子问题，保存子问题的解（记忆化或表格法）避免重复计算，从而显著降低复杂度。典型例子是 0/1 背包：在容量限制下选择物品使价值最大，用 dp[i][w] 表示前 i 个物品、容量 w 的最大价值，通过“选/不选”转移求解；另一个常见例子是最长公共子序列（LCS）。

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。