滴滴餐厅题思路
单纯听同学讲的题目，自己写了些但是没有OJ让我测试能不能AC；
就只说说思路，求大神指导。
就只说说思路，求大神指导。
动态规划+状态压缩
n个桌子，m个人；
dp定义为dp[m][2^n]
dp[i][j]中；
i表示第i个人
j表示的是一个压缩的状态，
展开成二进制，如
例题中3个桌子，5个人；
m = 2^5 = 32;
n个桌子，m个人；
dp定义为dp[m][2^n]
dp[i][j]中；
i表示第i个人
j表示的是一个压缩的状态，
展开成二进制，如
例题中3个桌子，5个人；
m = 2^5 = 32;
j取0~31, j = 31 表示 11111这个状态，
既每个位子都可以坐；
既每个位子都可以坐；
递推关系为：
dp[i][j] = max(dp[i-1][j - 2^index] + money[i],dp[i-1][j])
index表示选择的座位，减去2^index相当于从j中删除了2进制该位置的1;
dp[i][j] = max(dp[i-1][j - 2^index] + money[i],dp[i-1][j])
index表示选择的座位，减去2^index相当于从j中删除了2进制该位置的1;
桌子状态压缩成二进制后解决。
360集团公司氛围 352人发布
