那么这个问题就可以用动态规划来解决

那么这个问题就可以用动态规划来解决。

要攻克一个动态规划问题，最重要的就是要找出它的状态转移方程，类似于下面这样：

思考的步骤分为5步：

确定变量，即函数有多少个输入参数，也就是父问题和子问题中会变化的变量。例如斐波那契数列，父问题f(5)f(5)f(5)和子问题f(4)f(4)f(4) 的区别就是nnn，因此状态就是nnn。斐波那契数列这个问题比较简单，只有一个变量，有的动规问题会有多个变量。

确定函数的返回值，一般就是题目所求的目标值。例如斐波那契数列，f(n)f(n)f(n)返回的是第n个斐波那契数。有的题目比较复杂，函数不是直接求解目标值，而是求解某种中间值。

确定可选动作，也就是如何驱动父问题转移成子问题。例如斐波那契数列，f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)f(n)=f(n−1)+f(n−2)，可选的动作有两种，减1和减2。

**确定递推方程，即父问题与子问题之间的等式关系。