Climbing Stairs (Pillələrə Qalxma)

Problem Təsviri

Siz n pillədən ibarət pilləkənin aşağısındasınız. Hər dəfə ya 1 pillə, ya da 2 pillə qalxa bilərsiniz. Zirvəyə çatmaq üçün neçə fərqli yol var?

Məsələn:

n = 2 üçün: 2 yol var (1+1 və ya 2)
n = 3 üçün: 3 yol var (1+1+1, 1+2, 2+1)
n = 4 üçün: 5 yol var (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

Pattern: Bu problem əslində Fibonacci ardıcıllığı ilə eynidir!

ways(n) = ways(n-1) + ways(n-2)

Müxtəlif Yanaşmalar

1. Sadə Rekursiya (Naive Approach)

Koda bax

public class ClimbingStairsNaive {
    
    public static int climbStairs(int n) {
        // Base cases
        if (n <= 2) {
            return n;
        }
        
        // From step n, we could have come from (n-1) or (n-2)
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
    
    public static void main(String[] args) {
        System.out.println("Climbing Stairs (Naive Recursion):");
        
        for (int i = 1; i <= 10; i++) {
            System.out.println("n = " + i + ", yollar = " + climbStairs(i));
        }
        
        // Performance test
        long startTime = System.currentTimeMillis();
        int result = climbStairs(35);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\nn = 35, yollar = " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

Time Complexity: O(2^n) - Eksponensial
Space Complexity: O(n) - Rekursiya stack-i üçün

Problemlər:

Böyük n dəyərləri üçün çox yavaş
Eyni alt-problemlər dəfələrlə hesablanır

2. Memoization (Top-Down DP)

Koda bax

import java.util.HashMap;
import java.util.Map;

public class ClimbingStairsMemoization {
    
    // Using HashMap for memoization
    private static Map<Integer, Integer> memo = new HashMap<>();
    
    public static int climbStairs(int n) {
        // Base cases
        if (n <= 2) {
            return n;
        }
        
        // Check if already computed
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // Compute and store result
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        memo.put(n, result);
        
        return result;
    }
    
    // Alternative implementation with array
    public static int climbStairsArray(int n) {
        if (n <= 2) return n;
        
        int[] memo = new int[n + 1];
        return climbStairsHelper(n, memo);
    }
    
    private static int climbStairsHelper(int n, int[] memo) {
        if (n <= 2) {
            return n;
        }
        
        if (memo[n] != 0) {
            return memo[n];
        }
        
        memo[n] = climbStairsHelper(n - 1, memo) + climbStairsHelper(n - 2, memo);
        return memo[n];
    }
    
    public static void main(String[] args) {
        System.out.println("Climbing Stairs (Memoization):");
        
        for (int i = 1; i <= 20; i++) {
            System.out.println("n = " + i + ", yollar = " + climbStairs(i));
        }
        
        // Clear memo for performance test
        memo.clear();
        
        // Performance test
        long startTime = System.currentTimeMillis();
        int result = climbStairs(100);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\nn = 100, yollar = " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

Time Complexity: O(n) - Hər dəyər yalnız bir dəfə hesablanır
Space Complexity: O(n) - Memo table və rekursiya stack-i

3. Tabulation (Bottom-Up DP)

Koda bax

public class ClimbingStairsTabulation {
    
    public static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        // Create DP table
        int[] dp = new int[n + 1];
        
        // Base cases
        dp[1] = 1; // 1 way to reach step 1
        dp[2] = 2; // 2 ways to reach step 2
        
        // Fill table bottom-up
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
    
    // Method to get all ways for steps 1 to n
    public static int[] getAllWays(int n) {
        if (n <= 0) return new int[0];
        
        int[] ways = new int[n + 1];
        
        if (n >= 1) ways[1] = 1;
        if (n >= 2) ways[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2];
        }
        
        return ways;
    }
    
    public static void main(String[] args) {
        System.out.println("Climbing Stairs (Tabulation):");
        
        // Get all ways
        int[] ways = getAllWays(20);
        for (int i = 1; i < ways.length; i++) {
            System.out.println("n = " + i + ", yollar = " + ways[i]);
        }
        
        // Performance test
        long startTime = System.currentTimeMillis();
        int result = climbStairs(100);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\nn = 100, yollar = " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

Time Complexity: O(n)
Space Complexity: O(n) - DP table üçün

4. Space Optimized (O(1) Space)

Koda bax

public class ClimbingStairsOptimized {
    
    public static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        int prev2 = 1; // ways(1)
        int prev1 = 2; // ways(2)
        int current = 0;
        
        for (int i = 3; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
    
    // Alternative implementation with clearer variable names
    public static int climbStairsClear(int n) {
        if (n <= 2) return n;
        
        int oneStepBefore = 2;  // ways(n-1)
        int twoStepsBefore = 1; // ways(n-2)
        
        for (int i = 3; i <= n; i++) {
            int current = oneStepBefore + twoStepsBefore;
            twoStepsBefore = oneStepBefore;
            oneStepBefore = current;
        }
        
        return oneStepBefore;
    }
    
    public static void main(String[] args) {
        System.out.println("Climbing Stairs (Space Optimized):");
        
        for (int i = 1; i <= 20; i++) {
            System.out.println("n = " + i + ", yollar = " + climbStairs(i));
        }
        
        // Performance test
        long startTime = System.currentTimeMillis();
        int result = climbStairs(100);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\nn = 100, yollar = " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

Time Complexity: O(n)
Space Complexity: O(1) - Yalnız bir neçə dəyişən

5. Genişləndirilmiş Versiya (k Addım)

Koda bax

public class ClimbingStairsKSteps {
    
    // Hər dəfə 1-dən k-ya qədər pillə qalxa bilərsinizsə
    public static int climbStairsK(int n, int k) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[0] = 1; // 0-cı pilləyə çatmağın 1 yolu var (başlanğıc)
        
        for (int i = 1; i <= n; i++) {
            // i-ci pilləyə (i-1), (i-2), ..., (i-k) pillələrdən gələ bilərik
            for (int j = 1; j <= k && j <= i; j++) {
                dp[i] += dp[i - j];
            }
        }
        
        return dp[n];
    }
    
    // Space optimized version
    public static int climbStairsKOptimized(int n, int k) {
        if (n <= 1) return 1;
        
        // Sliding window approach
        int[] window = new int[k];
        window[0] = 1; // ways(1)
        
        int sum = 1;
        
        for (int i = 2; i <= n; i++) {
            int newWays = sum;
            
            if (i <= k) {
                newWays += 1; // can reach from step 0
            } else {
                sum -= window[i % k]; // remove oldest
            }
            
            sum += newWays;
            window[i % k] = newWays;
        }
        
        return window[(n - 1) % k];
    }
    
    public static void main(String[] args) {
        System.out.println("Climbing Stairs with K Steps:");
        
        int n = 10;
        for (int k = 1; k <= 5; k++) {
            System.out.println("n = " + n + ", k = " + k + ", yollar = " + climbStairsK(n, k));
        }
        
        System.out.println("\nNümunə: n = 5, k = 3");
        System.out.println("Yollar = " + climbStairsK(5, 3));
    }
}

Mürəkkəblik:

Time Complexity: O(n*k)
Space Complexity: O(n) və ya O(k) optimized versiyada

Practical Nümunə

Koda bax

public class ClimbingStairsWithCost {
    
    // Hər pilləyə qalxmağın bir dəyəri var
    // Minimum dəyərlə zirvəyə çatın
    // LeetCode 746: Min Cost Climbing Stairs
    
    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        
        if (n <= 1) {
            return 0;
        }
        
        // dp[i] = i-ci pilləyə çatmağın minimum dəyəri
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
        }
        
        // Zirvəyə son pillədən və ya ondan əvvəlki pillədən çata bilərik
        return Math.min(dp[n - 1], dp[n - 2]);
    }
    
    // Space optimized version
    public static int minCostOptimized(int[] cost) {
        int n = cost.length;
        
        if (n <= 1) return 0;
        
        int prev2 = cost[0];
        int prev1 = cost[1];
        
        for (int i = 2; i < n; i++) {
            int current = cost[i] + Math.min(prev1, prev2);
            prev2 = prev1;
            prev1 = current;
        }
        
        return Math.min(prev1, prev2);
    }
    
    public static void main(String[] args) {
        System.out.println("Min Cost Climbing Stairs:");
        
        int[] cost1 = {10, 15, 20};
        System.out.println("Cost array: [10, 15, 20]");
        System.out.println("Minimum cost: " + minCostClimbingStairs(cost1));
        
        int[] cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println("\nCost array: [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]");
        System.out.println("Minimum cost: " + minCostClimbingStairs(cost2));
    }
}

Performance Müqayisəsi

Koda bax

public class ClimbingStairsComparison {
    
    public static void comparePerformance() {
        int[] testCases = {10, 20, 30, 40, 50};
        
        System.out.println("Performance Müqayisəsi:");
        System.out.println("n\tNaive\t\tMemo\t\tTabulation\tOptimized");
        
        for (int n : testCases) {
            System.out.print(n + "\t");
            
            // Naive (only for small n)
            if (n <= 40) {
                long start = System.nanoTime();
                ClimbingStairsNaive.climbStairs(n);
                long end = System.nanoTime();
                System.out.print((end - start) / 1000 + "μs\t\t");
            } else {
                System.out.print("Too slow\t");
            }
            
            // Memoization
            long start = System.nanoTime();
            ClimbingStairsMemoization.climbStairs(n);
            long end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs\t\t");
            
            // Tabulation
            start = System.nanoTime();
            ClimbingStairsTabulation.climbStairs(n);
            end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs\t\t");
            
            // Optimized
            start = System.nanoTime();
            ClimbingStairsOptimized.climbStairs(n);
            end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs");
            
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        comparePerformance();
    }
}

Müsahibə Sualları

1. Əsas Problem

Sual: n pilləyə qalxmaq üçün neçə yol var? (hər dəfə 1 və ya 2 pillə) Cavab: Space optimized DP - O(n) time, O(1) space.

2. K Addım Variantı

Sual: Hər dəfə 1-dən k-ya qədər pillə qalxa bilərsinizsə? Cavab: dp[i] = sum(dp[i-1] + dp[i-2] + ... + dp[i-k])

3. Minimum Dəyər

Sual: Hər pilləyə qalxmağın dəyəri varsa, minimum dəyərlə necə qalxırıq? LeetCode: Problem 746 - Min Cost Climbing Stairs

4. Məhdudiyyətlər

Sual: Bəzi pillələr qırılıbsa və oradan keçə bilmirsinizsə? Cavab: DP-də həmin indeksləri 0 olaraq qeyd etmək.

5. Konkret Yolun Tapılması

Sual: Yalnız sayı deyil, konkret yolları necə tapmaq olar? Cavab: Backtracking və ya path reconstruction istifadə etmək.

LeetCode Problemləri

70. Climbing Stairs - https://leetcode.com/problems/climbing-stairs/ (Əsas problem)
746. Min Cost Climbing Stairs - https://leetcode.com/problems/min-cost-climbing-stairs/ (Dəyər əlavə edilib)
1137. N-th Tribonacci Number - https://leetcode.com/problems/n-th-tribonacci-number/ (3 addım variantı)
91. Decode Ways - https://leetcode.com/problems/decode-ways/ (Oxşar DP pattern)
1269. Number of Ways to Stay in the Same Place - https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/ (Daha mürəkkəb variant)

Real-World Tətbiqləri

Path Planning: Robot hərəkət planlaması
Game Development: Oyunçunun hərəkət variantları
Resource Allocation: Addım-addım resurs bölgüsü
Financial Planning: İnvestisiya strategiyaları (mərhələli)
Network Routing: Şəbəkədə alternativ yollar

Optimizasiya Məsləhətləri

Böyük n üçün: Space optimized version istifadə edin
Çoxlu sorğu: Tabulation ilə pre-compute edin
K addım variantı: Sliding window texnikası
Modular arithmetic: Overflow-dan qaçınmaq üçün
Path reconstruction: Əlavə array ilə konkret yolu saxlamaq

Əlaqəli Problemlər

Fibonacci Numbers
House Robber
Decode Ways
Jump Game
Unique Paths

Problem Təsviri​

Müxtəlif Yanaşmalar​

1. Sadə Rekursiya (Naive Approach)​

2. Memoization (Top-Down DP)​

3. Tabulation (Bottom-Up DP)​

4. Space Optimized (O(1) Space)​

5. Genişləndirilmiş Versiya (k Addım)​

Practical Nümunə​

Performance Müqayisəsi​

Müsahibə Sualları​

1. Əsas Problem​

2. K Addım Variantı​

3. Minimum Dəyər​

4. Məhdudiyyətlər​

5. Konkret Yolun Tapılması​

LeetCode Problemləri​

Real-World Tətbiqləri​

Optimizasiya Məsləhətləri​

Əlaqəli Problemlər​

Problem Təsviri

Müxtəlif Yanaşmalar

1. Sadə Rekursiya (Naive Approach)

2. Memoization (Top-Down DP)

3. Tabulation (Bottom-Up DP)

4. Space Optimized (O(1) Space)

5. Genişləndirilmiş Versiya (k Addım)

Practical Nümunə

Performance Müqayisəsi

Müsahibə Sualları

1. Əsas Problem

2. K Addım Variantı

3. Minimum Dəyər

4. Məhdudiyyətlər

5. Konkret Yolun Tapılması

LeetCode Problemləri

Real-World Tətbiqləri

Optimizasiya Məsləhətləri

Əlaqəli Problemlər