蓝桥杯必备——动态规划“路径问题”以及这种题的小结(一)

简介: 蓝桥杯必备——动态规划“路径问题”以及这种题的小结

回顾java数组部分知识

int[][]m=new int[2][3] 表达的含义是,两行,三列。

一、不同路径

不同路径

首先这个题我们分五步走

1.状态表示(按照经验+题目要求)

一般都是以···为结尾或者以···为起始

这道题我们就以dp[i][j]为他要求的到达结尾有多少条路径

此时你要思考一个东西,有多少条路径,他是怎么来的来考虑第二个状态转移方程

2.状态转移方程

3.初始化

初始化我们采用相当于取巧的一个方式,采用虚拟节点,我们看到上面的状态转移方程,可能就思考一件事,我们会不会出现越界现象,比如最上面的那几个,无法进行-1操作的。

所以我们用虚拟节点,给你包一下,目的是不让他产生越界,红色的都是虚拟的

但是我们使用虚拟节点是有规则的:

1.虚拟节点里面的值,需要保证后面填表是正确的。

那么来思考一下,怎么虚拟节点的格子怎么处理呢,首先你要清楚一件事情,假如只有起点,也就是1*1,那么是不是只有一种,所以要保证起点是1,那么假如是1*2,1*3,是不是也只有一种走法,就是从起点一直向右走,那么再来想出现2*1,的话是不是起点只能往下走,也就只有一种走法,以此类推,所以只需要保证dp[0][1]=1或者dp[1][0]=1,二者不可都为1啊

2.下标的映射,原先表和这个表的对应关系

4.填表顺序

从上倒下,从左到右,

5.返回值

dp[i][j]

最后代码之前,给大家整一下数组,

double[]mark=new double[5],其中的下表是0,1,2,3,4。

这是对应的完整代码

class Solution {
    public int uniquePaths(int m, int n) {
     int [][]dp=new int[m+1][n+1];
     dp[0][1]=1;
     for(int i=1;i<m+1;i++){
     for(int j=1;j<n+1;j++){
     dp[i][j]=dp[i-1][j]+dp[i][j-1];
     }
}
return dp[m][n];
    }
}

二、不同路径II

不同路径II

这个题也是一样五步走,

1.状态表示(按照经验+题目要求)

一般都是以···为结尾或者以···为起始

这道题我们就以dp[i][j]为他要求的到达结尾有多少条路径

此时你要思考一个东西,有多少条路径,他是怎么来的来考虑第二个状态转移方程。

2.状态转移方程

还是我们的那个dp[i][j]=d[i-1][j]+dp[i][j-1],但是这个题和上一个题有区别,就是这个题多个障碍物,我们该如何处理这个障碍物呢?

我的刚开始做的时候很迷惑,在想这个障碍物改咋整,假如他不是我的终点,但是他又正好在经过终点的路上。其实这是我思维的一个误区,因为我其实已经选定好从结尾开始看了。

从结尾看就两种情况:

1.障碍物在终点处:在终点,肯定就到不了,就是0呗

2.障碍物不在终点:不在终点就是要想,他正常是左边的+上面的,遇到障碍物就和上面一样,视为0即可

3初始化:和上面一样。

4.填表顺序

从上倒下,从左到右,

5.返回值

dp[i][j]

这里在引入一个小知识

(int[][] ob) {

int m=ob.length,n=ob[0].length;

当二维数组的时候,m表示二维数组的列,n表示行数

class Solution {
    public int uniquePathsWithObstacles(int[][] ob) {
     int m=ob.length,n=ob[0].length;
     int[][]dp=new int[m+1][n+1];
     dp[0][1]=1;
     for(int i=1;i<m+1;i++){
         for(int j=1;j<n+1;j++){
//这里容易产生一个误区,考虑原来数组是0的部分,我刚开始是考虑1的所以导致想不明白假如我是1,我给障碍物赋值为0,问题障碍物本身就0。
//然后看一眼题解,发现是把没有石头的部分,去那么算
             if(ob[i-1][j-1]==0){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
             }
         }
     }
return dp[m][n];
    }
}
class Solution {
    public int uniquePathsWithObstacles(int[][] ob) {
     int m=ob.length,n=ob[0].length;
     int[][]dp=new int[m+1][n+1];
     dp[0][1]=1;
     for(int i=1;i<m+1;i++){
         for(int j=1;j<n+1;j++){
             if(ob[i-1][j-1]==1){
//我按照我的想法来一遍,发现不是误区,其实也是对的,只是说,这个需要赋值为0(不写赋值也可)之后,就要跳到下一个,不然的话,他就相当于没有障碍物了
                 dp[i][j]=0;
                 continue;
             }
             dp[i][j]=dp[i-1][j]+dp[i][j-1];
         }
     }
return dp[m][n];
    }
}


相关文章
|
13天前
|
机器学习/深度学习 算法 C++
【DFS/回溯算法】2016年蓝桥杯真题之路径之谜详解
题目要求根据城堡北墙和西墙箭靶上的箭数,推断骑士从西北角到东南角的唯一路径。每步移动时向正北和正西各射一箭,同一格不重复经过。通过DFS回溯模拟“拔箭”过程,验证路径合法性。已知箭数约束路径唯一,最终按编号输出行走顺序。
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
9月前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
228 5
蓝桥杯-动态规划专题-子数组系列,双指针
蓝桥杯-动态规划专题-子数组系列,双指针
蓝桥杯动态规划-第五弹 最大子数组和 买卖股票最佳时机IV 第N个泰波那契数 环形数组
蓝桥杯动态规划-第五弹 最大子数组和 买卖股票最佳时机IV 第N个泰波那契数 环形数组
蓝桥杯动态规划第三弹-路径问题进阶2.0
蓝桥杯动态规划第三弹-路径问题进阶2.0
蓝桥杯必备动态规划第二弹-路径问题进阶
蓝桥杯必备动态规划第二弹-路径问题进阶
蓝桥杯必备——动态规划“路径问题”以及这种题的小结(二)
蓝桥杯必备——动态规划“路径问题”以及这种题的小结