动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。利用各个阶段之间的关系，逐个求解，最终求得全局最优解，需要确认原问题与子问题、动态规划状态、边界状态、边界状态结值、状态转移方程。 案例：三角形的动态规划（求解最大值） 在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100，数字为 0 - 99
输入格式： 5 //表示三角形的行数 接下来输入三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 要求输出最大和①计算最后一行，因此可以把最后一行直接写出，如下图：
②分析倒数第二行的每一个数，现分析数字2，2可以和最后一行4相加，也可以和最后一行的5相加，但是很显然和5相加要更大一点，结果为7，我们此时就可以将7保存起来，然后分析数字7，7可以和最后一行的5相加，也可以和最后一行的2相加，很显然和5相加更大，结果为12，因此我们将12保存起来。以此类推。我们可以得到下面这张图： ③然后按同样的道理分析倒数第三行和倒数第四行，最后分析第一行，我们可以依次得到如下结果： ⑤ 上面的推导过程相信大家不难理解，理解之后我们就可以写出如下的递推型动态规划程序： 程序代码：
package lanqiao; import java.util.Scanner; public class test_12_三角形问题DP { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] a = new int[101][101]; int[][] max = new int[101][101]; for (int i = 1; i <= n ; i++) { for (int j = 1; j <= i; j++) { a[i][j] = sc.nextInt(); } } for (int i = 1; i <= n; i++) { max[n][i] = a[n][i]; } for (int i = n-1; i >= 1 ; --i) { for (int j = 1; j <= i; ++j) { if (n == 1) { max[i][j] = a[i][j]; }else { max[i][j] = Math.max(max[i+1][j], max[i+1][j+1])+a[i][j]; } } } System.out.println(max[1][1]); } }具体详情请见：https://blog.csdn.net/baidu_28312631/article/details/47418773?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.channel_param
