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

时间:2024-01-10 01:06:00 标签:  算法  算法  动态规划  贪心算法  自底向上的动态规划  自顶向下的动态规划  

文章目录

  • 一、动态规划简介
  • 二、自底向上的动态规划示例
    • 1、原理分析
    • 2、算法设计
    • 3、代码示例
  • 三、自顶向下的动态规划示例
    • 1、算法设计
    • 2、代码示例




一、动态规划简介



动态规划 , 英文名称 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);
    }
}

执行结果 :

三角形最短路径为 6

在这里插入图片描述

来源:https://blоg.сsdn.nеt/hаn1202012/аrtiсlе/dеtаils/128197591

智能推荐

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xf

标签:算法  

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法

标签:动态规划  算法  

动态规划是对暴力递归算法的优化&#xff0c;主要是通过数组记录的方法&#xff0c;

标签:动态规划  代理模式  算法  

在复习动态规划时发现了几道有趣的题&#xff0c;与大家分享一下&#xff01;

标签:动态规划  算法  

买卖股票相关的动态规划题目

标签:动态规划算法  c++  动态规划  算法  后端  

前言&#xff1a;首先&#xff0c;什么是动态规划&#xff1f;      

标签:数据结构与算法  动态规划  算法  

T1:一个数组 中的最长 升序 子序列 的长度 给你一个整数数组 num

标签:数据结构和算法相关  动态规划  数据结构  算法  

大家好&#xff0c;我是耀星&#x1f31f;&#xff0c;欢迎来

标签:动态规划  算法  java  动态规划  

猜你喜欢

题目描述 有一个教授有一批一模一样的鹰蛋。有一天他来到了一栋楼的脚下&#xff0

标签:动态规划  算法  

预习准备

标签:动态规划  

本文章中的例题全部来自力扣  参考视频&#xff1a;代码随想录动态规划之完全背包&

标签:算法  数据结构  leetcode  动态规划  

第4章-动态规划 总分&#xff1a;100分 得分&#xff1a;

标签:# 算法设计与分析  动态规划  算法  数据结构  

Search当一个大问题是由多个子问题构成时,我们可以通过不断分解问题来最终构建我们想求的大问题。这个过程成为搜索(Search)。搜索空间(Search Space)可以用Tree的形式展现出来,便于理解。时间复杂度取决于这棵树的深度和每个node的children个数。Search 最重要的就是定义好状态,保证每个子问题都能用一个状态来描述Search没有重复子问题,但DP有。DP(Dynamic Programming)如果我们Search Space有重复子问题的话,可以记录下这些子问题的答案来保证不会重复计算多次。所以DP也被称为Search+Me

标签:题型  算法  动态题型  算法  动态  

  参考&#xff1a;代码随想录

标签:动态规划  算法  

参考&#xff1a;代码随想录 300.最长递

标签:算法  动态规划  

什么是动态规划&#xff1a;动态规划_百度百科 内容太多了不作介绍&#xff0c;

标签:算法  数据结构  c++  动态规划  

198.打家劫舍 1. dp数组&#xff08;d

标签:算法  动态规划  

相关问题

相关文章

热门文章

推荐文章

相关标签