@ninijia 在 Leetcode每日一题练习 ------ 2466. 统计构造好字符串的方案数 中发帖
从Leetcode 每日一题练习继续讨论:
2466. 统计构造好字符串的方案数
2466. Count Ways To Build Good Strings
题解
本题仍是动态规划问题,考虑每次都可以append zero次0或者one次1,则在新append后可以得到的新数字的组合个数取决于append前的组合个数,即假设当前的下标为m,设到下标p的可能的组合方法有dp[p]种,则到下标m处可能的组合数量为dp[m-zero]+dp[m-one]。
从头开始遍历数组,对每个下标处的组合个数都使用上面的公式进行计算,对于小于0的下标则直接忽略。注意最终结果要模给定的大整数。
代码
class Solution {
public:
int countGoodStrings(int low, int high, int zero, int one) {
ve...