网站发布内容是否过滤,网络营销网站建设设计方案,爱站网使用的是什么网站,wordpress载入动画数位DP的大致思想#xff1a;枚举每一位能选取的合法值。
1. LC 2376 统计特殊整数
说是DP#xff0c;但实际上状态转移方程挺难写的#xff0c;毕竟是枚举集合论#xff0c;这里就不贴状态转移方程了。总体的写法其实是搜索记忆化。之所以称之为DP#xff0c;是因为枚举每一位能选取的合法值。
1. LC 2376 统计特殊整数
说是DP但实际上状态转移方程挺难写的毕竟是枚举集合论这里就不贴状态转移方程了。总体的写法其实是搜索记忆化。之所以称之为DP是因为
对于第i位 如果[0,i-1]位全部都选的能选的最大值那么第i位最多也就只能选到最大值注意第0位肯定是受限制的否则第i位能随便选如果前面[0,i-1]位都是0前导零这一位就可以随便选了
有这两大状态转移的规则所以还是被称之为DP。细节写在代码里了
import java.util.Arrays;class Solution {char[] s;int[][] memo;public int countSpecialNumbers(int n) {s Integer.toString(n).toCharArray();// 记搜// memo[i][mask]代表[0,i-1]位选掉了mask中各个索引位置代表的数的情况下后面有多少个特殊整数memo new int[s.length][110];for (int i 0; i memo.length; i) {Arrays.fill(memo[i],-1); // -1 代表没有计算过}// 一开始第一位当然要受限制不过也可以是前导零所以 (true,false)return f(0,0,true,false);}/*** 记搜计算在确定[0,i-1]位后剩下的有种特殊整数的情况* param i 第i位* param mask 已经选择了mask集合中的数* param isLimit 当前位上限是否有限制有的话是 int(s[i]),没有的话是9* param isNum 当前位是否跳过即前导零* return 确定[0,i-1]位后剩下的有种特殊整数的情况*/private int f(int i,int mask,boolean isLimit,boolean isNum){if(is.length){return isNum ?1:0; // 防止从头到尾的前导零这种情况根本不是个数字当然不能算}/*这个!isLimit条件非常重要举个例子n420假设现在前两位选了 4,2那么mask {4,2}第三位就只能选0但如果前两位选了24mask{4,2}第三位可以随便选除了2,4)在第一种情况下能选1种第二种情况下能选8种10-2差了7种情况而之后的循环枚举会考虑所有顶着最大上限选的情况所以如果当前这个数位受到最大上限的限制的话后面的for循环会统计这个情况的而不是把非受限制的情况的记忆化搜索结果返回在这个例子里dp[2][{2,4}] 8 而不是1但isNum不是必须判断的因为如果前面都受限制后面一位也一定受限制可前面都是前导零不代表后面也得是前导零况且[0,i-1]位全是前导零的情况顶多出现一次后面再怎么递归都不可能有的*/if(!isLimit memo[i][mask]!-1){return memo[i][mask];}int res 0;if(!isNum){// 含前导零跳过res f(i1,mask,false,false);}// 当前位置是否受限制int upper isLimit?s[i]-0:9;// 枚举可以填充的数,这里要检查是否之前使用了前导零使用了的话要去掉之前if(!isNum)加过了没有用的话可以从0开始for (int j isNum?0:1; j upper; j) {// 特殊整数要求各数位都不一样所以检查mask中之前用过没// mask就是个位图比如 binary(mask) 0101010111 从右往左看用集合论表示就是 {8,6,4,2,1,0} 这些数字已经被用过了if((maskj1)0){// 用掉j就是把mask的第j位设置为0 mask|(1j)// 那么下一个数位是否受限制呢如果当前数位受限制并且当前数位选取了上限那么下一位是受限制的否则不受限制// 例如n 123 i1假设当前数位不受上限那么也就是说这个数99下一位当然也不受限制// 但若受限制则代表前面i0的时候选择了上限1i1选择最多是2下一位自然受限制最大是3// 最后既然这一位枚举了一位有意义的数字后续的枚举自然也是有意义的, isNum 为 trueres f(i1,mask|(1j),isLimit jupper,true);}}// 记忆化if(!isLimit){memo[i][mask] res;}return res;}
}2. LC 233 数字1的个数
这题是我学了板子后做的第一题真的汗流浃背。想想做做调调卡了1h才出来。
首先这个跟上面一题的区别是对于枚举的数字没有限制。不仅没有重复性的限制而且还没有前导零的限制前导零的数不会被判无效因为这道题只看1的数量
这样就简便了不少。我们只需要看是否被上限限制即可。这个是否受限还是和以前一样只有前面的都受限本次才会受限否则不会。
令f(i,isLimit)表示第[i,n-1]位在Limit的限制下能产生的1的数量。那么本轮的上限可以由isLimit计算得出 如果upper1也就是upper0的情况本轮不可能选1 如果upper1本轮选择1会产生 int(suffix(n,i1))1 个1。其中suffix(n,i1)代表n的[i1,n-1]位的值例如 n 2132 , i1 那么suffix(2232,2) 32。 这是比较显然的拿上面那个例子来说如果本轮选择1后续会有2100到2132这些数的第i1位是1所以就是32-00133个 如果upper1本轮选择1会产生 pow(10,n-i-1)个1。例如n2232,i1,那么如果本轮选择1就会有2100到2199的第i1位是1也就是pow(4-1-1)100个
以上考虑的是本轮第i位产生的1的数量。后面[i1,n-1]产生的还没算
两种情况讨论。上限是upper说明本轮有upper种选择其中可能有一种是顶格选的isLimit情况有upper种是非顶格选的。依次累加到res即可。这里对于前者根据当前的isLimit来如果当前顶格了后面也得顶格当前不顶格后面也不顶格根据后者isLimit false
最后记搜的时候要记得排除顶格选的情况。因为这种情况已经被统计过了。
import java.util.Arrays;class Solution {char[] s;int[] memo;public int countDigitOne(int n) {s Integer.toString(n).toCharArray();memo new int[s.length];Arrays.fill(memo,-1);return f(0,true);}/*** 记搜计算[0,i-1]位选择完毕后后面的位置总共能出现多少个1* param i 第i位* param isLimit 受到最大上限限制与否* return [0,i-1]位选择完毕后后面的位置总共能出现多少个1*/private int f(int i,boolean isLimit){if(is.length){return 0;}/*例如n 1230 现在 i[0,1,2] {1,2,3},那么后面一个1都不可能有但如果i[0,1,2] {1,2,2}后面是可以有一个1的memo记录的是后者*/if(!isLimit memo[i]!-1){return memo[i];}int res 0;int upper isLimit?s[i]-0:9;// 如果这一轮选1if(upper1){res suffix(i1)1;}else if(upper1){res (int) Math.pow(10,s.length-i-1);}// 本来可以选 upper1个数这一轮// 如果之前全部都顶格选了那么将是upper个可以后续不用顶格选的和一个必须顶格选的res upper*f(i1,false) f(i1,isLimit);if(!isLimit){memo[i] res;}return res;}private int suffix(int start){StringBuilder sb new StringBuilder();for(int istart;is.length;i){sb.append(s[i]);}return sb.isEmpty()?0:Integer.parseInt(sb.toString());}
}3. LC 2719 统计整数数目
这道题我思路有的但就是有点歪所以虽然A了但是时间上表现不好
首先我的记搜是包含4个状态的定义 f (i,isLower,isUpper,acc)表示在[0,i-1]位均已枚举且数位和为acc且是否受下限与上限的制约的情况下后续能够产生的符合条件的数。
那么上限和下限分别怎么算我通过补齐较小的num1的前导零使其与num2在数位长度上等长。这样下限由num1补齐前导零后决定上限由num2决定。
在深搜时记忆化在不受上下限制约的情况下在枚举到第i位且已有数位累计和acc的情况下后续能有多少个符合条件的数。
之后根据是否受上下限制约枚举数位即可。这里注意枚举时可以及时地判断是否已经爆掉数位和上界了而下界可以留到最终递归基的是否判断。
最后我现在是觉得模运算这个东西有很强的性质加法乘法的性质都特别强如果担心答案爆了怎么办就在能取模的地方全部取模就行。
import java.util.Arrays;class Solution {static long mod (long)1e97;char[] s1;char[] s2;long[][] memo;int min;int max;public int count(String num1, String num2, int min_sum, int max_sum) {min min_sum;max max_sum;s1 supplyLeadingZero(num1,num2).toCharArray();s2 num2.toCharArray();// memo[i][acc]代表在不受限制的情况下 到了第i位已经有acc的数位和第[i1,n-1]位最多能有多少个符合条件的数memo new long[s2.length][22*91];for (int i 0; i memo.length; i) {Arrays.fill(memo[i],-1L);}return (int) (f(0,true,true,0) % mod);}private String supplyLeadingZero(String num1,String num2){StringBuilder num1Builder new StringBuilder(num1);while(num1Builder.length()num2.length()){num1Builder.insert(0, 0);}num1 num1Builder.toString();return num1;}private long f(int i,boolean isLower,boolean isUpper,int acc){if(is2.length){return accmin?1L:0L;}if(!isLower !isUpper memo[i][acc]!-1){return memo[i][acc];}int lb isLower?s1[i]-0:0;int ub isUpper?s2[i]-0:9;long res 0L;for(int jlb;jub;j){if(maxaccj){res (res%mod f(i1,isLower jlb, isUpper jub, accj)%mod) % mod;}}if(!isLower !isUpper){memo[i][acc] res;}return res;}
}还有一种更常见的思路是先统计一遍≤num1的情况再统计一遍≤num2的情况然后后者减前者就是(num1,num2]的情况。又因为题目是闭区间所以单独判一下num1符合条件与否即可。这种思路跑得比我的代码快这里摘录一份
class Solution {private static final int MOD 1_000_000_007;public int count(String num1, String num2, int minSum, int maxSum) {int ans calc(num2, minSum, maxSum) - calc(num1, minSum, maxSum) MOD; // 避免负数int sum 0;for (char c : num1.toCharArray()) {sum c - 0;}if (minSum sum sum maxSum) {ans; // num1 是合法的补回来}return ans % MOD;}private int calc(String s, int minSum, int maxSum) {int n s.length();int[][] memo new int[n][Math.min(9 * n, maxSum) 1];for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(0, 0, true, s.toCharArray(), minSum, maxSum, memo);}private int dfs(int i, int sum, boolean isLimit, char[] s, int minSum, int maxSum, int[][] memo) {if (sum maxSum) { // 非法return 0;}if (i s.length) {return sum minSum ? 1 : 0;}if (!isLimit memo[i][sum] ! -1) {return memo[i][sum];}int up isLimit ? s[i] - 0 : 9;int res 0;for (int d 0; d up; d) { // 枚举当前数位填 dres (res dfs(i 1, sum d, isLimit (d up), s, minSum, maxSum, memo)) % MOD;}if (!isLimit) {memo[i][sum] res;}return res;}
}
