魔法深渊
魔法深渊
http://www.nowcoder.com/questionTerminal/55e34723b1d34c42af83b39de2395408
题目难度：二星
考察点：动态规划、预处理
方法1：暴力、动态规划
- 分析：
这个题很像之前的跳台阶：一共有n个台阶，青蛙只能跳1阶或者是2阶，问有多少种跳法？跳台阶思路如下:
假设青蛙跳n个台阶的跳法为f(n)那么：
如果第一次跳的是1阶，那么剩下的n-1个台阶，跳法是f(n-1)
如果第一次跳的是2阶，那么剩下的n-2个台阶，跳法是f(n-2)
由此可得：f(n) = f(n-1) + f(n-2)
当n=1时，f(1) = 1
当n=2时，f(2) = 2
至此，跳台阶问题已经解决。
对于这道题来说的话，我们可以借助之前的想法，假设月神有f(n)种方法能够跳出深渊，那么就有：
如果第一次跳的是2^0阶，那么剩下的n-2^0个台阶，就有f(n-2^0)种跳法。
如果第一次跳的是2^1阶，那么剩下的n-2^1个台阶，就有f(n-2^1)种跳法。
...
如果第一次跳的是2^k阶，那么剩下的n-2^k个台阶，就有f(n-2^k)种跳法。
其中k为不超过n的2的次幂的指数最大值。
那么由此可得：f(n) = f(n-2^0) + f(n-2^1) + ... + f(n-2^k)
当n=0时，f(0) = 1。
算法实现：
(1). 用一个数组p表示2的幂，其中p[i]=2^i
(2). 输入n，然后从1遍历到n，在来一个内层循环j表示2^j，然后如果i >= p[j]， dp[i] += dp[i-p[j]]，不要忘记取模
(2). 输出结果dp[n]。
2. 复杂度分析：
时间复杂度：O(n^2log(n))空间复杂度：O(n)
3. 代码：
#include
using namespace std;
typedef long long LL;
int p[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
const int MAXN = 1e3+5;
const int MOD = 1e9+3;
LL dp[MAXN];
int main() {
int m; cin>>m;
while(m--) {
int n; cin>>n;
memset(dp, 0, sizeof dp);
dp[0] = 1;
for(int i=1; i<=n; i++) {
for(int j=0; j<10; j++) {
if(i < p[j]) break;
dp[i] = (dp[i] + dp[i-p[j]]) % MOD;
}
}
cout<<dp[n]<<endl;
}
return 0;
} 方法2：预处理、动态规划
-
分析：
其实在上述的代码中，我们其实没有必要在m层循环中，每次都计算一遍dp[n]，这样是浪费时间的，我们可以提前预处理一下dp[n]的计算方法，这样在循环中只需要输入一个n，输出一个dp[n]即可，具体详见代码。 -
复杂度分析：
时间复杂度：O(max(nlog(n), m))
空间复杂度：O(n) -
代码：
#include using namespace std; typedef long long LL; int p[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512}; const int MAXN = 1e3+5; const int MOD = 1e9+3; LL dp[MAXN]; void Init() { dp[0] = 1; for(int i=1; i<MAXN; i++) { for(int j=0; j<10; j++) { if(i < p[j]) break; dp[i] = (dp[i] + dp[i-p[j]]) % MOD; } } } int main() { int m; cin>>m; Init(); while(m--) { int n; cin>>n; cout<<dp[n]<<endl; } return 0; }
