数位dp
https://leetcode.cn/problems/reverse-bits-lcci/description/
public int reverseBits(int num) {
int max = 0;
int dp1 = 0;
int dp2 = 0;
for (int i = 0; i < 32; i++) {
if ((num & 1) == 1){
dp1++;
dp2++;
}else {
dp2 = dp1 + 1;
dp1 = 0;
}
if (dp2 > max) max = dp2;
num = num >> 1;
}
return max;
}
总结:动态规划的题 从低位向高位走, num & 1用来判断当前最后一位是不是1,也可以判断当前的数字是奇还是偶, dp1代表从低位到当前位全是1的长度,dp2代表从低位到当前位变了1次之后的长度,所以如果当前位是1,dp1,dp2都可以++,如果是0,那dp2等于上一位的dp1,也就是dp1,dp1置为0,。
标签:dp2,dp1,int,max,++,num,dp,数位 From: https://www.cnblogs.com/jeasonGo/p/18102714