##### Short Problem Definition:

Emma is playing a new mobile game involving clouds numbered from 1 to n. There are two types of clouds, ordinary clouds and thunderclouds. The game ends if Emma jumps onto a thundercloud, but if she reaches the last cloud, she wins the game!

##### Link

##### Complexity:

time complexity is O(N)

space complexity is O(N)

##### Execution:

Theoretically your solution can depend on the fact that the win condition is guaranteed, but I don’t like such solutions. Here I present a semi-DP approach that keeps track of the optimal number of jumps it takes to reach each cloud.

##### Solution:

[rust]

use std::io;

use std::cmp;

fn get_number() -> u32 {

let mut line = String::new();

io::stdin().read_line(&mut line).ok().expect("Failed to read line");

line.trim().parse::<u32>().unwrap()

}

fn get_numbers() -> Vec<u32> {

let mut line = String::new();

io::stdin().read_line(&mut line).ok().expect("Failed to read line");

line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()

}

fn calculate_jumping(a: Vec<u32>, n: usize) -> u32{

let mut v = vec![100; n];

v[0] = 0;

for i in 1..n {

//println!("{} {} {:?}", i, a[i], v);

if a[i] == 1 {

continue;

}

if i == 1 {

v[i] = v[i-1] + 1;

} else {

v[i] = cmp::min(v[i-1], v[i-2]) + 1;

}

}

v[n-1]

}

fn main() {

let n = get_number() as usize;

let a = get_numbers();

println!("{}", calculate_jumping(a, n) );

}

[/rust]

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.