LeetCode 3693 | Climbing Stairs II | Java | Medium | Dynamic Programming | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3693 — Climbing Stairs II using Dynamic Programming in Java.
In this problem, we are given a staircase with n + 1 steps numbered from 0 to n and a 1-indexed cost array representing the cost of landing on each step. Starting from step 0 with an initial cost of 0, we can jump from step i to step i + 1, i + 2, or i + 3. The total cost incurred by a jump from step i to step j equals the landing step cost plus the square of the jump distance. Our goal is to determine the minimum cumulative cost required to reach the final step n.
We design an optimal 1D Dynamic Programming solution where dp[j] stores the minimum cost to reach step j. For each step j from 1 to n, we evaluate transitions from the valid previous steps j - 1, j - 2, and j - 3, adding the landing fee and the quadratic jump penalty d * d. By bounding each state evaluation to at most 3 constant-time checks, we achieve an optimal O(n) linear runtime with O(n) auxiliary space, easily optimizable to O(1) space using a 3-element rolling window.
🔥 Problem Highlights
✅ Dynamic Programming formulation: dp[j] represents the minimum cost to reach step j
✅ 3-step transition window: jumps are constrained to lengths 1, 2, and 3
✅ Quadratic jump penalty: jump cost incorporates distance squared plus destination step cost
✅ Base case and boundary handling: dp[0] equals 0 and lookback checks ensure step index remains non-negative
✅ Constant transition time: each step evaluates at most 3 candidate states in O(1) time
✅ Optimal complexity: O(n) linear time complexity and O(n) space complexity, reducible to O(1) rolling state
⏱️ TIMESTAMPS
00:00 Intro & Day 108 Streak Celebration
00:40 Problem Understanding & Staircase Rules
01:37 Core Insight: Quadratic Penalty & 3-Step Lookback
02:36 4-Step Dynamic Programming Strategy
03:44 Optimal Java 17 Solution Walkthrough Line by Line
05:36 Test Cases Walkthrough & Day 108 Streak Celebration
06:10 Time Complexity Analysis (O(N) Linear Time)
06:53 Space Complexity Analysis (O(N) / O(1) Auxiliary Space)
07:33 Summary & Outro!
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/November/10-November/3693-Climbing-Stairs-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/10-November/3693-Climbing-Stairs-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/10-November/3693-Climbing-Stairs-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/10-November/3693-Climbing-Stairs-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/10-November/3693-Climbing-Stairs-II/solution.js
🔗 LeetCode Source Code
📌 https://codebytushu.com/leetcode/problem/climbing-stairs-ii
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Dynamic Programming
Rolling Window
State Transitions
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does finding the minimum cost to land on step j only require checking at most 3 preceding steps?
1️⃣ From any step i, allowed jump lengths are strictly 1, 2, or 3
2️⃣ Quadratic penalties become negative beyond 3 steps
3️⃣ Larger jumps are automatically skipped by the compiler
4️⃣ Dynamic programming only works for three transitions
#LeetCode3693 #LeetCode #ClimbingStairsII #Java #JavaDSA #DynamicProgramming #Array #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3693 — Climbing Stairs II using Dynamic Programming in Java.
In this problem, we are given a staircase with n + 1 steps numbered from 0 to n and a 1-indexed cost array representing the cost of landing on each step. Starting from step 0 with an initial cost of 0, we can jump from step i to step i + 1, i + 2, or i + 3. The total cost incurred by a jump from step i to step j equals the landing step cost plus the square of the jump distance. Our goal is to determine the minimum cumulative cost required to reach the final step n.
We design an optimal 1D Dynamic Programming solution where dp[j] stores the minimum cost to reach step j. For each step j from 1 to n, we evaluate transitions from the valid previous steps j - 1, j - 2, and j - 3, adding the landing fee and the quadratic jump penalty d * d. By bounding each state evaluation to at most 3 constant-time checks, we achieve an optimal O(n) linear runtime with O(n) auxiliary space, easily optimizable to O(1) space using a 3-element rolling window.
🔥 Problem Highlights
✅ Dynamic Programming formulation: dp[j] represents the minimum cost to reach step j
✅ 3-step transition window: jumps are constrained to lengths 1, 2, and 3
✅ Quadratic jump penalty: jump cost incorporates distance squared plus destination step cost
✅ Base case and boundary handling: dp[0] equals 0 and lookback checks ensure step index remains non-negative
✅ Constant transition time: each step evaluates at most 3 candidate states in O(1) time
✅ Optimal complexity: O(n) linear time complexity and O(n) space complexity, reducible to O(1) rolling state
⏱️ TIMESTAMPS
00:00 Intro & Day 108 Streak Celebration
00:40 Problem Understanding & Staircase Rules
01:37 Core Insight: Quadratic Penalty & 3-Step Lookback
02:36 4-Step Dynamic Programming Strategy
03:44 Optimal Java 17 Solution Walkthrough Line by Line
05:36 Test Cases Walkthrough & Day 108 Streak Celebration
06:10 Time Complexity Analysis (O(N) Linear Time)
06:53 Space Complexity Analysis (O(N) / O(1) Auxiliary Space)
07:33 Summary & Outro!
📂 Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/November/10-November/3693-Climbing-Stairs-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/10-November/3693-Climbing-Stairs-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/10-November/3693-Climbing-Stairs-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/10-November/3693-Climbing-Stairs-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/10-November/3693-Climbing-Stairs-II/solution.js
🔗 LeetCode Source Code
📌 https://codebytushu.com/leetcode/problem/climbing-stairs-ii
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Dynamic Programming
Rolling Window
State Transitions
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does finding the minimum cost to land on step j only require checking at most 3 preceding steps?
1️⃣ From any step i, allowed jump lengths are strictly 1, 2, or 3
2️⃣ Quadratic penalties become negative beyond 3 steps
3️⃣ Larger jumps are automatically skipped by the compiler
4️⃣ Dynamic programming only works for three transitions
#LeetCode3693 #LeetCode #ClimbingStairsII #Java #JavaDSA #DynamicProgramming #Array #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
