Java实现动态规划经典题目

动态规划入门请看：
DP动态规划专题（一）动态规划基本模型

前言

【说明】

关于动态规划的见解：动规和递归有很多相似的地方，最显著的特征可以说是阶段性，二者都有很明显的阶段划分，所以，声明好每一个阶段所需要做的事情以及阶段与阶段之间的转移可以说是重中之重了，这就涉及几个问题，第一，需要声明好方法（递归）或者数组（动规）具体的意义，所代表的作用；第二，需要说明好递归处理数据的方式（递归）或者是阶段转移方程（动规）。第三，跳出方法的条件（递归）或者是数组边界条件（动规）。处理好这三个方面，基本上就没有问题，剩下的就是一些边边角角的问题。

【提炼】

• 声明数组代表的含义
• 状态转移方程
• 边界条件

代码

1.数字金字塔

【题目】

观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。

在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。
【输入】：
第一个行包含R(1<= R<=1000)，表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
【输出】：
单独的一行，包含那个可能得到的最大的和。
【样例输入】：
5 //数塔层数
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
【样例输出】：
86

【代码1】

	/**
     * 顺推 dp
     * 含义：f[x][y] 从0,0到x,y最大值
     * 方程：f[x][y] = max{f[x-1][y],f[x-1][y-1]} + a[x][y]
     * 边界：f[0][0] = a[0][0]
     * */
    public int positive(int[][] a) {
   
        int[][] f = new int[a.length][a.length];
        // 边界
        f[0][0] = a[0][0];

        // 状态转移方程
        int i,j;
        for (i=1; i<a.length; i++) {
   
            for (j=0; j<=i; j++) {
   
                /*判断是否数组越界,左右两边需单独处理*/
                if (j == 0) {
   
                    f[i][j] = f[i-1][j] + a[i][j];
                } else if (j == i) {
   
                    f[i][j] = f[i-1][j-1] + a[i][j];
                } else {
   
                    int max = f[i-1][j] > f[i-1][j-1] ? f[i-1][j] : f[i-1][j-1];
                    f[i][j] = max + a[i][j];
                }
            }
        }

        // 获取最大值
        int temp = 0;
        for (i=0; i<a.length; i++) {
   
            if (f[a.length-1][i] > temp) {
   
                temp = f[a.length-1][i];
            }
        }