动态规划类似于分治法，通过组合子问题的解来解决原问题，但动态规划应用于子问题重叠的场景。不必要的重复工作。
问：买长钢筋，剪成短钢筋出售。不同长度的钢筋对应不同的价格，希望能得到最好的切割方案，实现利润最大化。
长度我
价格 p
1
5
8
9
10
17
17
20
24
30
以4寸钢筋为例：
通过动态规划，每次寻找子问题的最优解，长度依次为1、2、3。. . . 从钢筋长度的最优解中得到已知解，从而找到除了已知解之外的从小到大遍历子问题的最优解，从而实现问题的解。
建立结果数组r[]来存放已知问题的最优解钢材切割 算法，每次p[i]的值存放在q个临时变量中进行比较。使用长度为 4 进行以下分析：
(1)当i的长度为1时，最优解为1，
（2）当i长度为2时，最优解为2（不除） 首先钢材切割 算法，得到q=5和已知长度为1的值。最优解为1+r[ij]=2，最优解不分可得解
(3)当i的长度为3时，最优解为3（不除），q= 8 =p[3]+r[0] =8 , q=8>p[2]+r[1] =6 , q=8>p[1]+r[2]=6
(4)当i的长度为4时，最优解为4=2+2,q=9=p[4]+r[0],q=9=p[3]+r[1],q =9
p[1]+r[3]=9
代码显示如下：
package com.ep.rabbitmq.test;
import java.util.Scanner;
public class Cut {
public static void main(String [] args)
{
int []p={0,1,5,8,9,10,17,17,20,24,30};
int []r=new int[p.length];
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
//分四步动态规划 分别求长度1到4的最优解
for (int i=1;i
// r[i-j]中存放的是已知问题的最优解，而且相对于p[j]的价值最大，因为p[j]和q[i-j] 下标相加i
// 满足下标长度为i的固定长度，从而实现了已知问题部分最优解，求子问题的最优解直到算出答案。
q=Math.max(q,p[j]+r[i-j]);
}
r[i]=q;
}
System.out.println(r[n]);
}
}
