虎牙C++笔试分享
编程三道题
分享下第三题的水dp写法
求0-n之间二进制内没有连续三个1的数的个数
#include <iostream> using namespace std; int v[100]; int dp[100][3]; int dfs(int len,int flag,bool limit){ if (flag == 3) return 0; if (len == 0) return 1; if (!limit&&dp[len][flag] != -1) return dp[len][flag]; int maxx = limit ? v[len] : 1; int cnt = 0; for (int i = 0; i <= maxx; i++){ if (i == 0){ cnt += dfs(len-1,0,limit&&i == v[len]); } else{ cnt += dfs(len-1, flag+1 , limit&&i == v[len]); } } return limit ? cnt : dp[len][flag] = cnt; } int solve(long long x){ memset(v, 0, sizeof(v)); int k = 0; while (x){ v[++k] = x % 2; x >>=1; } return dfs(k, 0, true); } int main(){ memset(dp, -1, sizeof(dp)); long long a; cin >> a; cout<<solve(a)<<endl; return 0; }
#虎牙直播##笔试题目##题解#