BudiBadu Logo

Festival Glow Step Combinations

Dynamic Programming Hard 0 views
Like24

The festival installs a glowing ramp of length n boards and performers may ascend the ramp using steps from a curated list of sizes To keep the choreography smooth the size of each step taken must be at least as large as the previous step no sudden backward pacing allowed The troupe wants to know how many distinct nondecreasing step sequences reach the ramp's end exactly so they can program matching lighting arcs and coordinate live musicians You receive n and a list of allowed positive step sizes Steps may repeat but the sequence must be nondecreasing and sum precisely to n Return the number of valid sequences modulo 1_000_000_007 using dynamic programming that progresses through the ramp while tracking the last step size if n is zero count the empty sequence as one calm ascent Avoid modifying the original list so the logistics team can reuse it for other rehearsals When the task involves connectivity or route cost build adjacency carefully and guard against revisiting stale states Use a visited or best-distance structure to avoid repeated work and ensure unreachable scenarios return the required fallback value instead of partial traversal results At hard difficulty hidden tests usually combine scale with edge behavior so the implementation must be both asymptotically efficient and logically strict Define transitions unambiguously prevent stale-state contamination and confirm tie-breaking or fallback rules are encoded directly in the core algorithm For implementation quality keep the function deterministic

Examples

Example 1
Input
n = 4, steps = [1,2]
Output
3
Explanation

Valid sequences are [1,1,1,1], [1,1,2], and [2,2].

Example 2
Input
n = 5, steps = [2]
Output
0
Explanation

No combination of nondecreasing steps sums to 5.

Example 3
Input
n = 3, steps = [1,3]
Output
2
Explanation

Sequences [1,1,1] and [3] satisfy the nondecreasing rule.

Algorithm Flow

Recommendation Algorithm Flow for Festival Glow Step Combinations - Budibadu
Recommendation Algorithm Flow for Festival Glow Step Combinations - Budibadu

Best Answers

java

import java.util.*;
class Solution {
    public int festival_glow_step_combinations(Object n, Object steps) {
        int target = (int) n;
        int[] s_arr = (int[]) steps;
        int MOD = 1000000007;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        Arrays.sort(s_arr);
        for (int s : s_arr) {
            for (int i = s; i <= target; i++) {
                dp[i] = (dp[i] + dp[i - s]) % MOD;
            }
        }
        return dp[target];
    }
}