题目描述

题解思路

题目可以转换成爬楼梯，即从第零层开始，每次能够向上爬zero层或者向上爬one层，最终能够爬到[low, high]层的种数总和
第n层是从第n - zero层或者第n - one层爬上来的，所以我们从最底层开始向上爬，记录过程中爬到每一层的方案数
当爬到[low, high]层内的时候进行结果计数

题解代码

rust">impl Solution {pub fn count_good_strings(low: i32, high: i32, zero: i32, one: i32) -> i32 {let m = 1_000_000_007;let mut f = vec![0; high as usize + 1];f[0] = 1;let mut ans = 0;for i in 1..=high {if i >= zero {f[i as usize] = f[(i - zero) as usize];}if i >= one {f[i as usize] = (f[i as usize] + f[(i - one) as usize]) % m;}if i >= low {ans = (ans + f[i as usize]) % m;}}ans}
}

题目链接

https://leetcode.cn/problems/count-ways-to-build-good-strings/