精华内容
下载资源
问答
  • 动态规划中有的题往往需要对dp数组斜着遍历,例如dp[ i ][ j ]的值主要由dp[ i ][ j-1 ]和dp[ i+1 ][ j ]两个值的大小决定,即向右上斜着遍历。 n = len(dp] for l in range(2, n+1): for i in range(0, n -l + 1):...

    如何斜着遍历一个二维数组

    动态规划中有的题往往需要对dp数组斜着遍历,例如dp[ i ][ j ]的值主要由dp[ i ][ j-1 ]和dp[ i+1 ][ j ]两个值的大小决定,即向右上斜着遍历。

    n = len(dp)
    for l in range(1, n):
    	for i in range(n - l):
    		j = l + i
    		dp[i][j] .....
    

    这样既可完成遍历
    可以看一个5 * 5的矩阵
    一个行,列都为5的矩阵
    在上图中,如果不考虑中间的对角线,只看右上角的斜线的话,对于5*5的二维数组,有4条斜线,表示我们要遍历4次。所以在第一层循环中的代码为
    for l in range(1, 5)

    那么 l 的值分别为1,2, 3,4

    再来看每次遍历时,行(i)的变化
    在第一次遍历时(l = 1),i 的位置依次为 0 1 2 3,遍历4行(5-1);
    在第二次遍历时(l = 2),i的位置依次为 0 1 2,遍历3行(5-2);
    在第三次遍历时(l = 3),i的位置依次为 0 1,遍历2行(5-3);
    在第四次遍历时(l = 4),i的位置依次为 0,遍历1行(5-4);
    所以 i 的可选范围是在range(5 - l)之中的,即:
    for i in range(5 - l)

    然后来看看列(j)的位置变化
    同上可知
    j = 1 2 3 4
    j = 2 3 4
    j = 3 4
    j = 4
    把l, i, j按如下排列一下:
    l = 1---------------2------3----- 4
    i = 0 1 2 3; 0 1 2; 0 1; 0
    j = 1 2 3 4; 2 3 4; 3 4; 4
    是不是可以看出 j = l + i
    把5给替换成n
    如此就推算出了斜着遍历的代码。

    如果需要考虑dp[i][i]该怎么写:

    还是以一个5*5的二维数组来看,考虑对角线的话,遍历次数就从5-1次变成了5次
    for l in range(5)

    按照上面的推算方式
    l = -----0----------1--------2-----3----4
    i = 0 1 2 3 4; 0 1 2 3; 0 1 2; 0 1; 0
    j = 0 1 2 3 4; 1 2 3 4; 2 3 4; 3 4; 4
    把5换成n,可以得出

    for l in range(n):
    	for i in range(n - l):
    		j =l + i
    		dp[i][j] .....
    

    那如果想遍历二维数组的左下角怎么办:

    这里同样是从 5 * 5长度推算到 n * n的长度,过程不表

    for l in range(n):
    	for i in range(l, n):
    		j = i - l
    		dp[i][j].....
    

    遍历二维数组的左上角:

    for l in range(n-1, -1, -1):
    	for i in range(l, -1, -1):
    		j = l - i
    		dp[i][j].....
    

    遍历二维数组的右下角:

    for l in range(n):
    	for i in range(n-1, l-1, -1):
    		j = n + l - i - 1
    		dp[i][j].....
    

    注意,这里无论是左上角还是右下角,所有的遍历方向都是从二维数组的左/右对角线开始的。如果想从顶点开始斜着遍历数组,把上面的代码稍微改一下即可。

    展开全文
  • 斜着遍历二维数组

    2020-10-16 19:16:40
    for(int l=2;l<=n;l++){ for(int i=0;i<=n-l;i++){ int j=i+n-1; } } 如数组 { {1,2,3}, {4,5,6}, {7,8,9}, } 遍历之后的结果是2,6,3。相当于遍历对角线上面的元素。
    for(int l=2;l<=n;l++){
    	for(int i=0;i<=n-l;i++){
    		int j=i+l-1;
    	}
    }
    

    如数组
    {
    {1,2,3},
    {4,5,6},
    {7,8,9},
    }
    遍历之后的结果是2,6,3。相当于遍历对角线上面的元素。

    展开全文
  • 本文参考书P113页代码,实现了右上和右下倾斜遍历二维数组,即: 代码 import static java.lang.System.out; public class Helloworld { public static void main(String[] args){ int n = 5; // 定义一个5*5...

    简介

    本文参考书P113页代码,实现了右上和右下倾斜遍历二维数组,即:
    在这里插入图片描述
    在这里插入图片描述

    代码

    import static java.lang.System.out;
    
    public class Helloworld {
    
        public static void main(String[] args){
            int n = 5;  // 定义一个5*5的矩阵
    
            out.println("右上倾斜遍历行列号");
            for (int l = 1; l <= n; l++) {  // 控制倾斜行数
                for (int i = 0; i <= n - l; i++) {  // 一行一行的打印
                    int j = l + i -1;
                    out.print("(" + i + ", " + j + ") ");
                }
                out.print("\n");
            }
    
            out.println("******************");
    
            out.println("右下倾斜遍历行列号");
            for (int l = 1; l <= n ; l++) {
                for (int j = 0; j <= n - l; j++) {  // 一列一列的打印
                    int i = l + j - 1;
                    out.print("(" + i + ", " + j + ") ");
                }
                out.print("\n");
            }
        }
    }
    

    如果你认为对你有用,关注我的微信公众号支持我一下吧!~

    在这里插入图片描述

    展开全文
  • 为什么动态规划遍历 dp 数组的方式五花八门,有的正着遍历,有的倒着遍历,有的斜着遍历。 1. 最优子结构 首先必须要明确一个问题:「最优子结构」是某些问题的一种特定性质,并不是动态规划问题专有的。 ...

    这篇文章就给你讲明白两个问题:

    1. 到底什么才叫 「最优子结构」,和动态规划什么关系
    2. 为什么动态规划遍历 dp 数组的方式五花八门,有的正着遍历,有的倒着遍历,有的斜着遍历。

    1. 最优子结构

    首先必须要明确一个问题:「最优子结构」是某些问题的一种特定性质,并不是动态规划问题专有的。 也就是说,很多问题其实都具有最优子结构(例如我们的贪心算法就具有最优子结构),只是其中大部分不具有重叠子问题,所以我们不把它们归为动态规划系列问题而已。

    1.1 直接最优子结构

    我先举个很容易理解的例子:

    假设你们学校有 10 个班,你已有的数据是10个班同学的所有成绩。现在,你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩,你会不会算?

    • 当然会,而且你不用重新遍历全校学生的分数进行比较,而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。

    我给你提出的这个问题就符合最优子结构:可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题,你知道所有子问题的答案后,就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。

    你看,这么简单的问题都有最优子结构性质,只是因为显然没有重叠子问题,所以我们简单地求最值肯定用不出动态规划。

    1.2 间接最优子结构

    再举个例子:

    假设你们学校有 10 个班,你已知计算了每个班的最大分数差(最高分和最低分的差值)。那么现在我让你计算全校学生中的最大分数差,你会不会算?

    • 可以想办法算,但是肯定不能通过已知的这 10 个班的最大分数差推到出来。因为这 10 个班的最大分数差不一定就包含全校学生的最大分数差,比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差。

    这次我给你提出的问题就不符合最优子结构,因为你没办通过每个班的最优值推出全校的最优值,没办法通过子问题的最优值推出规模更大的问题的最优值。想满足最优子结构,子问题之间必须互相独立。 全校的最大分数差可能出现在两个班之间,显然子问题不独立,所以这个问题本身不符合最优子结构。

    那么遇到这种最优子结构失效情况,怎么办?策略是:改造问题 。对于最大分数差这个问题,我们不是没办法利用已知的每个班的分数差吗,那我只能这样写一段暴力代码:

    int result = 0;
    for (Student a : school) {
        for (Student b : school) {
            if (a is b) continue;
            result = max(result, |a.score - b.score|);
        }
    }
    return result;
    

    改造问题,也就是把问题等价转化:最大分数差,不就等价于最高分数和最低分数的差么,那不就是要求最高和最低分数么,不就是我们讨论的第一个问题么,不就具有最优子结构了么?那现在改变思路,借助最优子结构解决最值问题,再回过头解决最大分数差问题,是不是就高效多了?

    当然,上面这个例子太简单了,不过请读者回顾一下,我们做动态规划问题,是不是一直在求各种最值,本质跟我们举的例子没啥区别,无非就是需要再处理一下重叠子问题。

    前文「不同定义不同解法」和「高楼扔鸡蛋进阶」就展示了如何改造问题,不同的最优子结构,可能导致不同的解法和效率。

    再举个常见但也十分简单的例子,求一棵二叉树的最大值,不难吧(简单起见,假设节点中的值都是非负数):

    int maxVal(TreeNode root) {
        if (root == null)
            return -1;
        int left = maxVal(root.left);
        int right = maxVal(root.right);
        return max(root.val, left, right);
    }
    

    你看这个问题也符合最优子结构,以 root 为根的树的最大值,可以通过两边子树(子问题)的最大值推导出来,结合刚才学校和班级的例子,很容易理解吧。

    当然这也不是动态规划问题,旨在说明,最优子结构并不是动态规划独有的一种性质,能求最值的问题大部分都具有这个性质;但反过来,最优子结构性质作为动态规划问题的必要条件,一定是让你求最值的,以后碰到那种恶心人的最值题,思路往动态规划想就对了,这就是套路。

    动态规划不就是从最简单的 base case 往后推导吗,可以想象成一个链式反应,以小博大。但只有符合最优子结构的问题,才有发生这种链式反应的性质。

    找最优子结构的过程,其实就是思考状态转移方程的过程,方程体现符合最优子结构,之后就可以写暴力解了,写出暴力解就可以看出有没有重叠子问题了,有则优化,无则 OK。这也是套路,经常刷题的朋友应该能体会。

    这里就不举那些正宗动态规划的例子了,读者可以翻翻历史文章,看看状态转移是如何遵循最优子结构的,这个话题就聊到这,下面再来看另外个动态规划迷惑行为。

    2. dp数组的遍历方向

    我相信读者做动态规问题时,肯定会对递推写法(这里不考虑递推写法的动态规划)的dp 数组的遍历顺序有些头疼。我们拿二维 dp 数组来举例,有时候我们是正向遍历(所谓正向遍历,就是从数组下标小的地方开始):

    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            // 计算 dp[i][j]
    

    有时候我们反向遍历:

    for (int i = m - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--)
            // 计算 dp[i][j]
    

    有时候可能会斜向遍历:

    // 斜着遍历数组
    for (int l = 2; l <= n; l++) {
        for (int i = 0; i <= n - l; i++) {
            int j = l + i - 1;
            // 计算 dp[i][j]
        }
    }
    

    甚至更让人迷惑的是,有时候发现正向反向遍历都可以得到正确答案,比如我们在「团灭股票问题」中有的地方就正反皆可。

    那么,如果仔细观察的话可以发现其中的原因的。你只要把住两点就行了:

    1. 遍历的过程中,所需的状态必须是已经计算出来的。
    2. 遍历的终点必须是存储结果的那个位置。

    下面来具体解释上面两个原则是什么意思。

    比如编辑距离这个经典的问题,详解见前文「编辑距离详解」,我们通过对 dp 数组的定义,确定了 base case 是 dp[..][0]dp[0][..],最终答案是 dp[m][n];而且我们通过状态转移方程知道 dp[i][j] 需要从 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 转移而来,如下图:
    在这里插入图片描述
    那么,参考刚才说的两条原则,你该怎么遍历 dp 数组?肯定是正向遍历:

    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            // 通过 dp[i-1][j], dp[i][j - 1], dp[i-1][j-1]
            // 计算 dp[i][j]
    

    因为,这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的,而且最终结束在我们想要的答案 dp[m][n]

    再举一例,回文子序列问题,详见前文 「子序列问题模板」 ,我们通过对 dp 数组的定义,确定了 base case 处在中间的对角线,dp[i][j] 需要从 dp[i+1][j], dp[i][j-1], dp[i+1][j-1]转移而来,想要求的最终答案是 dp[0][n-1],如下图:
    在这里插入图片描述
    这种情况根据刚才的两个原则,就可以有两种正确的遍历方式:
    在这里插入图片描述
    要么从左至右斜着遍历,要么从下向上从左到右遍历,这样才能保证每次 dp[i][j] 的左边、下边、左下边已经计算完毕,得到正确结果。

    现在,你应该理解了这两个原则,主要就是看 base case最终结果 的存储位置,保证遍历过程中使用的数据都是计算完毕的就行,有时候确实存在多种方法可以得到正确答案,可根据个人口味自行选择。

    可以像作者这样,画一张图来判断怎么进行遍历,这样更加清晰!

    3. 文章来源

    1. 动态规划答疑篇
    展开全文
  • 给定一张用二维数组表示的网格地图,其中1表示陆地单元格,0表示水域单元格。网格地图中的单元格视为水平/垂直相连(向不相连)。这个网格地图四周完全被水域包围,并且其中有且仅有一个岛(定义为一块或多块...
  • 先给大家分析一下问题,这道题可以简单的理解为在[n+1,n+1]大小的二维数组中的遍历问题,有点类似于图遍历的问题,但是与图遍历不同的是,一般图的遍历问题只能朝上下左右这四个方向走,而此题却有着包括上方的3...
  • 为什么动态规划遍历DP数组的方式有正着遍历,有倒着遍历,有斜着遍历? 最优子结构 最优子结构是某些问题的一种特定的性质,并不是动态规划问题所特有的. 很多问题都具有最优子结构,但是其中大部分不具有重叠子问题,...
  • 动态规划问题答疑

    2020-02-06 18:01:01
    2、为什么动态规划遍历 dp 数组的⽅式五花⼋门,有的正着遍历,有的倒 着遍历,有的斜着遍历。 一:.最优子结构一定要符合各个子问题间是相互独立而不是互相牵连互相制约的,比如你想要在考试中取得最优的成绩,...
  • 思路:定义g[i][j]为索引从i到j的字符串是否为回文串,斜着遍历一次即可初始化该数组。然后定义f[i]为索引从0到i为回文串的最小分割次数,根据g数组更新f。 class Solution { public int minCut(String s) { int...
  • leetcode给出的动态规划的 参考答案好像是横着遍历矩阵,我是斜着,从左上到右下遍历矩阵,这样就不用开二维数组了。 将矩阵按左上到右下的对角线分成两半。两个 (两层的for循环) ,分别用来遍历这两半。两层f
  • 用建立一个动态数组二维矩阵,再依次遍历动态数组里的字符就可以得到zigzag conversion。 而在整个过程中倒了很多次的就是关于这个题的数学表达式上,通过画图我大概制定了对应的表达式。如图。 当存竖的字符时...
  • C++迷宫寻路详解

    2020-05-22 19:15:25
    用一个5 × 5的二维数组,表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。 分析 1.使用一个比迷宫稍大的二维数组初始化为迷宫,简化...
  • m皇后(思路题目)

    2018-03-17 14:42:59
    这道题当初有两点没有想到,一点是不知道该如何处理斜着的方向,另一点是没想到只用求该直线上的两端点。 这题要开四个数组,分别记录该方向上的点的最左端和最右端。 然后遍历所有的点,遍历该点的四个方向(上下...
  • 搜索1011

    2019-09-22 21:36:53
    给出m,n的二阶矩阵,输入若干*或@,如果@的上下左右或者斜着相邻的的四个方向有@,则可以构成一块,求满足条件的块数 解题思路: 用dfs来做,定义一个方向数组,代表一个点的8个可能的方向,定义一个访问数组,...
  • P1101 单词方阵

    2019-11-02 23:51:36
    要求横着竖着斜着 我们首先要从这个二维数组中选择是y的地方 进入不像dfs的dfs然后横向竖向遍历这一行,如果等于这个字符串的下一位就继续,如果不是就return 如果cur等于7就说明找到了,然后全部vis标记为1证明这7个是...
  • 现在由陆地方块或者边界围成的有水方块视为一个水洼(单个有水方块也算),且只有水平或垂直方向连续的含水方块才能视为属于同一个水洼(斜着的不行),请计算这片土地上有多少个水洼。 输入:第一行两个整数m和n,...
  • 大话数据结构

    2019-01-10 16:35:22
    《璇玑图》共八百四十字,纵横各二十九字,纵、横、、交互、正、反读或退一字、迭一字读均可成诗,诗有三、四、五、六、七言不等,目前有人统计可组成七千九百五十八首诗。听清楚哦,是7958首。 第6章树 149 6.1...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    《璇玑图》共八百四十字,纵横各二十九字,纵、横、、交互、正、反读或退一字、迭一字读均可成诗,诗有三、四、五、六、七言不等,目前有人统计可组成七千九百五十八首诗。听清楚哦,是7958首。 第6章树 149 6.1...
  • 纵、横、、交互、正、反读或退一字、迭一字读均可成诗,诗有三、四、五、六、七言不等,目前有人统计可组成七千九百五十八首诗。听清楚哦,是7958首。 第6章 树 149 6.1 开场白 150 无论多高多大的树,那也是从小...
  • 《璇玑图》共八百四十字,纵横各二十九字,纵、横、、交互、正、反读或退一字、迭一字读均可成诗,诗有三、四、五、六、七言不等,目前有人统计可组成七千九百五十八首诗。听清楚哦,是7958首。 第6章树 149 6.1...

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

数组斜着遍历