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

这篇具有很好参考价值的文章主要介绍了【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 )。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、动态规划简介

动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ;

具体的算法都有具体的步骤 , 如 : 二分法 , 其有固定的解决步骤 , 先取一个中心点 , 判断解在左边还是右边 , 然后在一边再取一个中心点 , 再进行判定 , 该算法有具体的步骤 ;

动态规划 , 没有具体的步骤 , 只有一个核心思想 ;

动态规划的核心思想是由大化小 , 大规模问题使用小规模问题计算结果解决 , 类似于分治算法 ;

动态规划与贪心算法区别 :

动态规划 会为了长远利益损害当前利益 ; 动态规划不仅仅考虑下一步的利益 , 还对后面十几步甚至几十步进行了大量计算 , 得到了最佳结果 ;
贪心算法 只注重当前利益最大化 ; 贪心算法只考虑下一步的最佳利益 ;

动态规划实现方法 :

递归 : 如记忆化搜索的实现 ;
for 循环 : 使用多重 for 循环实现 ;

二、自底向上的动态规划示例

从下图的数字三角形中从上到下找到一条最短路径 ;

动态规划自底向上和自顶向下,算法,算法,动态规划,贪心算法,自底向上的动态规划,自顶向下的动态规划

1、原理分析

自底向上的动态规划思想 : 下面的 n 的最佳路径指的是以 n 为起点到达最底层的的最短路径 ;

顶部的 1 的最佳路径依赖于 2 和 3 中的最佳路径 , 选择最佳的路径即可 ;

2 的最佳路径依赖于 4 和 -5 中的最佳路径 ,
- 4 的最佳路径依赖于 7 和 8 中的最佳路径 ,
- -5 的最佳路径依赖于 8 和 9 中的最佳路径 ,
3 的最佳路径依赖于 -5 和 6 中的最佳路径 ,
- -5 的最佳路径依赖于 8 和 9 中的最佳路径 ,
- 6 的最佳路径依赖于 9 和 10 中的最佳路径 ,

最后一排中 ( 第四排 ) :

7 走到最底层的最小路径是其本身 7
8 走到最底层的最小路径是其本身 8
9 走到最底层的最小路径是其本身 9
10 走到最底层的最小路径是其本身 10

倒数第二排 ( 第三排 ) :

4 的最短路径从 7 和 8 之间取最短的最短路径 , 是 7 , 对应最短路径 7 , 最短路径为 4 + 7 = 11
-5 的最短路径从 8 和 9 之间取最短的最短路径 , 是 8 , 对应最短路径 8 , 最短路径为 -5 + 8 = 3
6 的最短路径从 9 和 10 之间取最短的最短路径 , 是 9 , 对应最短路径 9 , 最短路径为 6 + 9 = 15

倒数第三排 ( 第二排 ) :

2 的最短路径从 4 和 -5 之间取最短的最短路径 , 是 -5 , 对应最短路径 3 , 最短路径为 2 + 3 = 5
3 的最短路径从 -5 和 6 之间取最短的最短路径 , 是 -5 , 对应最短路径 3 , 最短路径为 3 + 3 = 6

倒数第四排 ( 第一排 ) :

1 的最短路径从 2 和 3 之间取最短的最短路径 , 是 2 , 对应最短路径 5 , 最短路径为 1 + 5 = 6

通过分析 , 可以得出从 1 开始的最短路径为 1 -> 2 -> -5 -> 8 , 最短路径为 6 ;

动态规划自底向上和自顶向下,算法,算法,动态规划,贪心算法,自底向上的动态规划,自顶向下的动态规划

2、算法设计

将下图的数据 , 存放到二维数组 triangle 中 , 作为数据源使用 ;

该 triangle 二维数组 ,

第 0 行有 1 个数字 ,
第 1 行有 2 个数字 ,
… ,
第 n-1 行有 n 个数字 ;

该二维数组的长度 , 就是数字三角形中的行数 ;

动态规划自底向上和自顶向下,算法,算法,动态规划,贪心算法,自底向上的动态规划,自顶向下的动态规划

状态记录 : 创建二维数组 dp , dp[i][j] 表示从第 i 行第 j 列的元素出发 , 数组的元素值就是走到最底层的最短路径 ;

dp 二维数组的作用就是用于记录状态值 , 如 :

dp[0][0] 表示从第 0 行第 0 列的 1 出发 , 走到最底层的最短路径 , 其值为 6 ;
dp[3][2] 表示从第 3 行第 2 列的 -5 出发 , 走到最底层的最短路径 , 其值为 3 ;

dp[0] 只有一个有效元素 , dp[1] 有两个有效元素 , dp[2] 有三个有效元素 , dp[4] 有四个有效元素 ;

初始化数据 : 假设该三角形有 n 行数据 ;

那么 , 第 n - 1 行 , 也就是最后一行 , 该 n - 1 行有 n 个数字 , i 取值 0 ~ n - 1 , 则 dp[n-1][i] 的值就是其本身 triangle[n-1][i]

数字三角形最后一行数字 , 即 n -1 行数字 , 作为初始化数据 ; 然后开始从 n - 2 行开始计算 ;

运算方程 : 设置具体的算法如何进行计算 , 从 n - 2 行开始计算本行数据的最短路径 ;

n - 2 行的第 i 个数字的最短路径 , 依赖于 n - 1 行的第 i 个数字和第 i + 1 个数字的最短路径 , 取较小的最短路径 ;

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

上述算法中二维数组 dp 中 , 每个元素 , 第 dp[i][j] 就是一个 子问题 , 表示数字三角形中第 i 行第 j 列元素的最短路径 , 通过这些子问题的解决 , 最终得到一个大规模问题的解决方案 ;

3、代码示例

代码示例 :

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

动态规划自底向上和自顶向下,算法,算法,动态规划,贪心算法,自底向上的动态规划,自顶向下的动态规划

三、自顶向下的动态规划示例

从下图的数字三角形中从上到下找到一条最短路径 ;

动态规划自底向上和自顶向下,算法,算法,动态规划,贪心算法,自底向上的动态规划,自顶向下的动态规划

每个点都有从起点开始走到该点的最短路径 ; 如

4 这个点 , 从起点 1 开始走 , 肯定走 1 -> 2 -> 4 路线是最短路径 , 为 7 ;
-5 这个点 , 从起点 1 开始走 , 肯定走 1 -> 2 -> -5 路线是最短路径 , 为 -2 ;

1、算法设计

状态记录 : 创建二维数组 dp , dp[i][j] 表示从起点走到第 i 行第 j 列的元素的最短路径 , 数组的元素值就是走到最底层的最短路径 ;

dp 二维数组的作用就是用于记录状态值 , 如 :

dp[0][0] 表示从起点第 0 行第 0 列的 1 出发 , 走到当前点第 0 行第 0 列的 1 的最短路径 , 其值为 1 ;
dp[3][2] 表示从起点第 0 行第 0 列的 1 出发 , 走到当前点第 3 行第 2 列的 -5 的最短路径 , 其值为 -2 ;

dp[0] 只有一个有效元素 , dp[1] 有两个有效元素 , dp[2] 有三个有效元素 , dp[4] 有四个有效元素 ;

初始化数据 : 没有办法套入动态规划方程中的点进行初始化操作 ;

在套用下面的运算方程时 , 会发现 , 最左侧的一排数字 , 没有左上角的元素 , 也就是第 i 行第 j 列的数字其左上角的数字是第 i - 1 行第 j - 1 列 , 如果 j = 0 , 那么左上角 j - 1 肯定为负数 ; 因此最左侧一列和最右侧一列是无法在运算方程中直接计算的 ;

此处初始化顶点的最短路径 , 和最左侧一列和最右侧一列数字的最短路径 ;

运算方程 : 设置具体的算法如何进行计算 , 从 n - 2 行开始计算本行数据的最短路径 ;

第 i 行第 j 列的数字 , 从顶点走到该点的最短路径 , 依赖于左上角第 i - 1 行第 j - 1 列的数字的最短路径 , 和右上角的第 i - 1 行第 j 列的数字的最短路径 , 找出上面二者最短路径较小的最短路径作为结果 ;

最终结果 : 在进行最后一层计算时 , 会得到第 n - 1 层 , 也就是最后一层 , 所有元素的最短路径 , 选择最小的最短路径 , 就是本次的最短路径 ;

上述算法中二维数组 dp 中 , 每个元素 , 第 dp[i][j] 就是一个 子问题 , 表示数字三角形中从起点开始到第 i 行第 j 列元素的最短路径 , 通过这些子问题的解决 , 最终得到一个大规模问题的解决方案 ;

2、代码示例

代码示例 :

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);
    }
}