如果你常刷leetcode，会发现许多问题带有Dynamic Programming的标签。事实上带有dp标签的题目有115道，大部分为中等和难题，占所有题目的12.8%（2018年9月），是占比例第二大的问题。
如果能系统地对dp这个topic进行学习，相信会极大地提高解题速度，对今后解决实际问题也有思路上的帮助。
本文以分杆问题为切入点，介绍动态规划的算法动机、核心思想和常用的两种实现方法。
分杆问题The rod-cutting problem（分杆问题）是动态规划问题的一个典例。
给出一根长度为n（n为整数）的杆，可以将杆切割为任意份长短不同的杆（其中包含完全不进行切割的情况），每一份的长度都为整数。给出一个整数数组p[]，p[i]表示长度为i的杆的价格，问如何对杆进行切割可以使利润最大。
p[]数组的一个示例如下：
在长度为n的杆上进行整数切割，共有2n-1种情况，因为有n-1个点可以选择是否切割。
将这些可以切割的点编号为1,2,3, ..., n-1，如果先试着在1处切割，则杆变成了长度为1和n-1的两段；如果试着在2处切割，则杆变为了长度为2和n-2的两段，以此类推，共有n种切法（包含完全不作切割）。这样，我们迈出了递归的第一步，即把长为n的杆的最优切割分成两个子问题：长为i的杆的最优切割和长为n-i的杆的最优切割（i = 1,2,...,n）。最终的利润为两个子杆的利润和。
如果用fn表示长度为n的杆切割后能得到的最大利润，经过以上分析，我们求取两个子杆的利润和的最大值即可。即
fn = max(pn, f1 + fn-1, f2 + fn-2, ..., fn-1 + f1).
这种思路是正确的，但不是太好，有心人可以注意到子问题之间有较大的重叠之处，比如计算fn-1时会需要查看f1 + fn-2，即f1 + fn-1这个子问题需要查看f1 + f1 + fn-2这个切法；而计算f2时又需要查看f1 + f1，即f2 + fn-2这个子问题也会查看到f1 + f1 + fn-2这个切法，相当于把一些可能性重复查看了多遍。
一个更简洁合理的思路是：设定左边这个长为ｉ的杆不可再切割，只有右边长为n-i的杆可以再切割。则问题变为
fn = max(pi + fn-i), i = 1,2,...,n
传统递归实现按照上面的分析，可以初步做一个递归实现如下：
1 int cutRod(int n, int[] p){ 2 if(n == 0) 3 return 0; 4 int max = Integer.MIN_VALUE; 5 for(int i = 1; i <= n; i++) 6 max = Math.max(max, p[i] + cutRod(n - i, p)); 7 return max; 8 }