Re: [閒聊] 每日leetcode
看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間11月前 (2024/12/30 22:03)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1230/1554 (看更多)
https://leetcode.com/problems/count-ways-to-build-good-strings
2466. Count Ways To Build Good Strings
一個好字串是一個長度low~high之間的字串，給你兩個長度分別是zero和one的全0字串和
全1字串，求出他們可以組合出幾種好字串。
思路:
沒啥好說的 就DP 類似上樓梯那樣，只是數字很大每次運算都要MOD而已，空間複雜度
好像可以壓?但我懶，我要去砍FGO的柱子惹。
java code
-------------------------------------------------
class Solution {
final int MOD = (int) (1e9 + 7);
public int countGoodStrings(int low, int high, int zero, int one) {
int res = 0;
int[] dp = new int[high + 1];
dp[0] = 1;
for (int i = 1; i <= high; i++) {
if (i - zero >= 0) {
dp[i] = (dp[i] + dp[i - zero]) % MOD;
}
if (i - one >= 0) {
dp[i] = (dp[i] + dp[i - one]) % MOD;
}
if (low <= i && i <= high) {
res = (res + dp[i]) % MOD;
}
}
return res;
}
}
-------------------------------------------------
--
https://i.imgur.com/5xKbxoh.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.191.3 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1735567433.A.AED.html
※ 編輯: Rushia (49.158.191.3 臺灣), 12/30/2024 22:08:34
討論串 (同標題文章)
完整討論串 (本文為第 1230 之 1554 篇)：