IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 931. 下降路径最小和 | 动态规划 | 暴力递归 | 自顶向下 -> 正文阅读

[数据结构与算法]931. 下降路径最小和 | 动态规划 | 暴力递归 | 自顶向下

力扣打卡:931. 下降路径最小和

解题思路

写动态规划,最重要的还是找出当前的状态和子问题状态之间的转移方程

状态转移的方程:一般都是题目中给定的行为或者动作

从题中分析:

找到第一行的最小下降路径和,给定的每一个节点都有三个路径(行为)

  • 左下角
  • 下角
  • 右下角

每一个节点的最小值都是这三个子问题中的最小值,加上自身的值,这个就是状态转移的过程

定义暴力递归函数的时候

  • 定义的函数就是可以求出子问题的结果
  • 写暴力递归函数不要想和任何的优化
  • 不要乱定义参数,必须要分析出一定结果后再进行编写
  • 一定要想着:自定义的函数就是可以得到结果的函数,用自定义的函数得到子问题结果与当前的状态进行连接
  • 状态转移方程就是:当前的状态和子问题状态之间的联系

代码

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        // 分析:每一个节点都可以向左下角,向下,右下角进行移动,每一个节点都会有一个最小值
        // 定义一个函数,这个函数可以得到每一个节点的最小值
        // int min = Integer.MAX_VALUE;
        // for(int i=0; i<matrix[0].length; i++){
        //     min = Math.min(min, planA(matrix, 0, i));
        // }
        // return min;

        int min = Integer.MAX_VALUE;
        int[][] memo = new int[matrix.length][matrix[0].length];
        for(int i=0; i<memo.length; i++){
            Arrays.fill(memo[i],10001); // 用无关的数据进行填充数组,方便进行判断
        }
        for(int i=0; i<matrix[0].length; i++){
            min = Math.min(min, planB(memo, matrix, 0, i));
        }
        return min;

    }

    // 定义一个函数,这个函数可以直接得到结果
    // 状态分析:当前的节点可以向左下角,下角,右下角进行转移,这三个子节点都由自己的最小值,以此类推
    // 定义的函数直接得到子问题的结果
    // 截至条件是:当索引越界或者已经到达了最后一行
    public int planA(int[][] matrix, int row, int col){

        if(col<0 || col>matrix[0].length-1) return Integer.MAX_VALUE; //  设置最大值,标记为不可达的目标

        if(row==matrix.length-1) return matrix[row][col]; // 在检测了col的基础上,如果发现row是在最后一行,那么直接返回自身的数据

        int left = planA(matrix, row+1, col-1); // 左下角的数据

        int bottom  = planA(matrix, row+1, col); // 下角数据

        int right = planA(matrix, row+1, col+1);

        return Math.min(left, Math.min(bottom, right)) + matrix[row][col];
    }

    // 写出了暴力递归的方式,自顶向下的动态规划也就是多了判断和记录的两个过程
    public int planB(int[][] memo, int[][] matrix, int row, int col){
        if(col<0 || col>matrix[0].length-1) return Integer.MAX_VALUE; // 如果索引越界,那么返回最大值,表示目标不可达
        if(row==matrix.length-1) return matrix[row][col]; // 在判断了col的基础上,如果发现了处于最后一行,那么直接返回数据

        if(memo[row][col] != 10001) return memo[row][col]; //将 memo 的数据置为与题目无关的数,方便进行判断

        int left = planB(memo, matrix, row+1, col-1); // 左下角
        int bottom = planB(memo, matrix, row+1, col); // 下角
        int right = planB(memo, matrix, row+1, col+1); // 右下角

        memo[row][col] = Math.min(left, Math.min(bottom, right)) + matrix[row][col]; // 加上自身的值,返回即可

        return memo[row][col];
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-14 16:12:59  更:2021-12-14 16:14:42 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 16:38:45-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码