以下哪些问题可以用动态规划解决A. 斐波那契数列B. 最短路径问题C. 最长公共子序列

动态规划的核心在于分解问题为子问题，利用重叠子问题和最优子结构性质，通过存储中间结果避免重复计算。

• 斐波那契数列：虽然递归效率低，但可通过动态规划（自底向上或记忆化）优化。
• 最短路径问题：如Floyd算法，通过逐步更新路径长度体现动态规划思想。
• 最长公共子序列：经典动态规划问题，通过二维数组记录子问题状态。

A. 斐波那契数列

动态规划思路：

1. 定义状态：dp[n]表示第n个斐波那契数。
2. 状态转移方程：dp[n] = dp[n-1] + dp[n-2]。
3. 初始化：dp[0] = 0, dp[1] = 1。
4. 自底向上计算，避免重复递归。

B. 最短路径问题

动态规划思路（以Floyd算法为例）：

1. 定义状态：dp[i][j]表示从节点i到节点j的最短路径长度。
2. 状态转移方程：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])（遍历所有中间节点k）。
3. 初始化：dp矩阵初始为边权值，不可达路径设为无穷大。
4. 逐步更新所有路径的最短值。

C. 最长公共子序列

动态规划思路：

1. 定义状态：dp[i][j]表示前i个字符的字符串A与前j个字符的字符串B的最长公共子序列长度。
2. 状态转移方程：
   • 若A[i] == B[j]，则dp[i][j] = dp[i-1][j-1] + 1。
   • 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3. 初始化：dp[0][j] = 0, dp[i][0] = 0。
4. 填表计算，最终dp[m][n]即为答案。