什么是动态规划算法？

先从小问题(重叠最优子结构)解决问题，将所有子结构解决后，该问题就解决了。

动态规划解题要点：状态：可以理解为重叠最优子结构的求解函数；状态转移方程：可以理解为如何依次求解重叠最优子结构函数完成最重问题的解决。通过例子解释动态规划：

题目：整数拆分。

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2

输出: 1

解释: 2 = 1 + 1, 1 × 1 = 1。

来源：力扣（LeetCode）链接：

1.画图列出所有拆分方法。

图1

2.解释说明。

由图可知，第一层分割是所有分割方案(p3*1, p2*2, p1*3)；此时求解max(p3*1, p2*2, p1*)即可解题。

但是p3、p2、p1都得求解，而从图中可看出，他们的求解都是重复子结构，所以可用递归求解。而递归是自上向下的解题思路。

如果把自上向下的解题思路反过来，自下向上解题，则可用动态规划求解：从最小问题开始，一步一步递推求解，最后解出总问题。

3.代码示例。

  int max2(int a, int b, int c) {  	return max(a, max(b, c));  }  int breakIntDp(int n){    vector<int> memo(n+1, -1);    //1. 求解memo[i]:将数字i分割后得到的最大乘积;    for (int i = 2; i <=n ; i++) {      //2. 对i分割成：j + (i-j)      for (int j = 1; j <= i-1; j++) {  //这层循环就是求解图1中那一层所有分割方案的最大乘积，也就是最优子结构.        memo[i] = max3(memo[i], j*(i-j), j*memo[i-j]);        }    }    return memo[n];  }