【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 )

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    /**
     * 三角形最短路径
     * @param triangle  三角形数据
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();

        // 动态规划状态 :
        // dp[i][j] 表示从 第 i 行 第 j 列的元素出发 ,
        // 数组的元素值就是走到最底层的最短路径 ;
        int[][] dp = new int[n][n];


        // 动态规划初始化 :
        // 第 n - 1 行 , 也就是最后一行 , 该 n - 1 行有 n 个数字 , i 取值 0 ~ n - 1 ,
        // 则 dp[n-1][i] 的值就是 其本身 triangle[n-1][i]
        // 数字三角形 最后一行 数字 , 即 n -1 行 数字 , 作为 初始化数据 ;
        // 然后开始从 n - 2 行开始计算 ;
        for (int i = 1; i < n; i++) {
            dp[n - 1][i] = triangle.get(n - 1).get(i);
        }

        // 动态规划方程 :
        // n - 2 行 的 第 i 个数字 的 最短路径 ,
        // 依赖于 n - 1 行 的 第 i 个数字 和 第 i + 1 个数字 的 最短路径 ,
        // 取较小的最短路径 ;
        for (int i = n - 2; i > -1; i--) {
            for (int j = 0; j < i + 1; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) // 先取一个最短路径最小值
                        + triangle.get(i).get(j);   // 再加上改点计算出一个新的最短路径
            }
        }

        // 动态规划结果 :
        // 使用上述 运算方程 从 第 n - 2 行 进行遍历 ,
        // 最终计算出 第 0 行 第 0 列 数字元素的最短路径 ,
        // 存储在二维数组 dp[0][0] 元素上 ;
        return dp[0][0];
    }


    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>(){
            {
                add(new ArrayList<Integer>(Arrays.asList(1)));
                add(new ArrayList<Integer>(Arrays.asList(2, 3)));
                add(new ArrayList<Integer>(Arrays.asList(4, -5, 6)));
                add(new ArrayList<Integer>(Arrays.asList(7, 8, 9, 10)));
            }
        };

        int minTotal = new Solution().minimumTotal(triangle);
        System.out.println("三角形最短路径为 " + minTotal);
    }
}

三角形最短路径为 6

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    /**
     * 三角形最短路径
     * @param triangle  三角形数据
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();

        // 动态规划状态 :
        // dp[i][j] 表示从 起点 走到 第 i 行 第 j 列的元素的最短路径 ,
        // 数组的元素值就是走到最底层的最短路径 ;
        int[][] dp = new int[n][n];


        // 动态规划初始化 : 没有办法套入 动态规划方程 中的点 进行初始化操作
        // 起始点的最短路径是其本身
        dp[0][0] = triangle.get(0).get(0);
        // 遍历 1 ~ n 行
        for (int i = 1; i < n; i++) {
            // 每行第 0 个元素的 最短路径 , 该元素没有左上角的点
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            // 每行第 n - 1 个元素的 最短路径 , 该元素没有右上角的点
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }

        // 动态规划方程 :
        // 第 i 行 第 j 列 的数字 , 走到该点的最短路径 ,
        // 依赖于 左上角 第 i - 1 行 第 j - 1 列 的 数字 的最短路径 ,
        // 和 正上方的 第 i - 1 行 第 j 列 的 数字 的 最短路径 ,
        // 找出 上面 二者 最短路径较小 的最短路径 作为结果 ;
        // 此处从 i = 2 开始 , 是因为 第一排的两个数字的最短路径已经初始化过了 , 在初始化中已经进行了初始化
        for (int i = 2; i < n; i++) {
            // j 的取值只能是 1 ~ i - 1 , 将每一行的 第 0 个 和 第 i 个 元素剔除出去
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
        }

        // 动态规划结果 :
        // 在进行最后一层 计算时 , 会得到 第 n - 1 层 , 也就是最后一层 , 所有元素的最短路径 ,
        // 选择 最小的 最短路径 , 就是本次的最短路径 ;
        int minTotal = dp[n - 1][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, dp[n - 1][i]);
        }
        return minTotal;
    }


    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>(){
            {
                add(new ArrayList<Integer>(Arrays.asList(1)));
                add(new ArrayList<Integer>(Arrays.asList(2, 3)));
                add(new ArrayList<Integer>(Arrays.asList(4, -5, 6)));
                add(new ArrayList<Integer>(Arrays.asList(7, 8, 9, 10)));
            }
        };

        int minTotal = new Solution().minimumTotal(triangle);
        System.out.println("三角形最短路径为 " + minTotal);
    }
}

三角形最短路径为 6