leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

climbing-stairs.dart (1100B)

      1 //Recurses through the number of possible ways one could climb a flight of
      2 //stairs if they can either step up by one or two each time.
      3 //TLE in Leetcode which is dumb because this is the most intuitive way to do it...
      4 //Time complexity of this is O(2^n) because each element added creates two more branches.
      5 //to conceptualize it think of a BST where each level has *2 more nodes.
      6 import 'dart:io';
      7 
      8 void main(){
      9     stdout.write("Enter a number: ");
     10     int val = int.parse(stdin.readLineSync()!);
     11     Solution sol = new Solution();
     12     print("There are " + sol.climbStairs(val).toString() + " ways to traverse those steps");
     13 }
     14 
     15 class Solution {
     16 
     17   int val = 0;  
     18   int climbStairs(int n) {
     19       recurse(0 , n);
     20       return val;
     21   }
     22     void recurse(int current_stair, int n){
     23         if(current_stair <= n - 2 ){
     24             recurse(current_stair + 1, n);
     25             recurse(current_stair + 2, n);
     26         }
     27         else if(current_stair <= n - 1){
     28             recurse(current_stair + 1 , n);
     29         }
     30         else if(current_stair == n){
     31             val += 1;
     32             
     33         }
     34     }
     35 
     36 }