蓝桥杯|蓝桥杯——算法训练——进击的青蛙蓝桥杯|动态规划|算法

问题描述
青蛙X正准备跳过一座桥，这座桥被划分为N段，记青蛙所在的起始点为0，桥的末端为N。桥上的一些点有一些石子，这些点是无法跳上去的。青蛙每次跳跃能向前跳跃+1，+2，+3段，现在请你算出跳到末端的总方法数。如果无法到达，请输出”No Way!"
输入格式
输入数据共N行。

第一行一个数字N，代表桥的长度。

接下来N行，表示从点1~N的道路情况，每行一个数字0或1，1表示有石子。
输出格式
输出一行，为一个整数，代表方法数，无法到达为“No Way!"
由于数据过大，我们只需要求出对 1000000007 的余数即可

一、dp
这题类似于那个爬楼梯问题和斐波那契问题，算是爬楼梯问题的改版，中间加入了障碍物和一次跳跃方式从两种变成了三种。
附：爬楼梯问题

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

class Solution { public int climbStairs(int n) { if (n <= 2) return n; int a = 1, b = 2, temp; for (int i = 3; i <= n; i++) { temp = a; a = b; b = temp + b; } return b; } }

这里的状态转移方程为：dp[i] = dp[i - 1] + dp[i - 2];

易知，本题状态转移方程为dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
但是这里用到了一维dp数组，用空间复杂度换取时间复杂度，导致最后一个测试点内存超限。

package com.study.蓝桥杯.算法训练; import java.util.Scanner; /** * @author sjn * @date 2022-2-22 */public class ALGO_965进击的青蛙 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N + 1]; for (int i = 1; i < N + 1; i++) { arr[i] = sc.nextInt(); }if (getRes(arr) == 0) { System.out.println("No Way!"); } else { System.out.println(getRes(arr)); }}public static long getRes(int[] arr) { int n = arr.length; long[] dp = new long[n]; dp[1] = arr[1] == 0 ? 1 : 0; dp[2] = arr[2] == 0 ? dp[1] + 1 : 0; dp[3] = arr[3] == 0 ? dp[1] + dp[2] + 1 : 0; for (int i = 4; i < n; i++) { if (arr[i] == 1) { dp[i] = 0; } else { dp[i] = (dp[i - 1] % 1000000007 + dp[i - 2] % 1000000007 + dp[i - 3] % 1000000007) % 1000000007; } }return dp[n - 1]; } }

文章图片

二、利用滚动数组优化dp算法
。。，还是内存超限了

package com.study.蓝桥杯.算法训练; import java.util.Arrays; import java.util.Scanner; /** * @author sjn * @date 2022-2-22 */public class ALGO_965进击的青蛙 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N]; for (int i = 0; i < N; i++) { arr[i] = sc.nextInt(); }long res = getRes(arr); if (res == 0) { System.out.println("No Way!"); } else { System.out.println(res); }}public static long getRes(int[] arr) { int n = arr.length; long[] dp = new long[3]; dp[0] = arr[0] == 0 ? 1 : 0; dp[1] = arr[1] == 0 ? dp[0] + 1 : 0; dp[2] = arr[2] == 0 ? dp[0] + dp[1] + 1 : 0; for (int i = 3; i < n; i++) { if (arr[i] == 1) { dp[i % 3] = 0; } else { dp[i % 3] = (dp[(i - 1) % 3] % 1000000007 + dp[(i - 2) % 3] % 1000000007 + dp[(i - 3) % 3] % 1000000007) % 1000000007; } }return dp[(n - 1) % 3]; } }

文章图片

三、利用滚动数组继续优化arr数组
介于方法二，仅利用滚动数组优化dp数组的话，最后一个测试点还是内存超限，那么我继续利用滚动数组优化arr数组，极大的降低了空间复杂度，但时间复杂度也相应的增大了，但是不影响AC
，所有测试点全部可以通过。

package com.study.蓝桥杯.算法训练; import java.util.Scanner; /** * @author sjn * @date 2022-2-22 */public class ALGO_965进击的青蛙 { static long[] dp = new long[3]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[3]; long res = 0; for (int i = 0; i < N; i++) { arr[i % 3] = sc.nextInt(); if (i == 2) {//第一轮输入，应该对dp数组进行初始化 dp[0] = arr[0] == 0 ? 1 : 0; dp[1] = arr[1] == 0 ? dp[0] + 1 : 0; dp[2] = arr[2] == 0 ? dp[0] + dp[1] + 1 : 0; } else if (i % 3 == 2 || i == N - 1) {//每一轮输入都要调用dp方法，以达到滚动数组优化arr数组的目的，极大的降低了空间复杂度 res = dp(arr, N); } }if (res == 0) { System.out.println("No Way!"); } else { System.out.println(res); }}/** * * @param arr存放数据的数组，长度为3 * @param n数据的总长度 * @return跳到末端的总方法数 */ public static long dp(int[] arr, int n) { for (int i = 0; i < 3; i++) { if (arr[i] == 1) { dp[i % 3] = 0; } else { dp[i % 3] = (dp[0] % 1000000007 + dp[1] % 1000000007 + dp[2] % 1000000007) % 1000000007; } }return dp[(n - 1) % 3]; } }