首页 > 试题广场 >

魔法深渊

[编程题]魔法深渊

热度指数：12473 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

前几个月放映的头号玩家简直火得不能再火了，作为一个探索终极AI的研究人员，月神自然去看了此神剧。

由于太过兴奋，晚上月神做了一个奇怪的梦，月神梦见自己掉入了一个被施放了魔法的深渊，月神想要爬上此深渊。

已知深渊有 N 层台阶构成，并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....)，请你编程告诉月神，月神有多少种方法爬出深渊

数据范围： $1 \le n \le 1000 \$ ，输入的数据组数满足 $1 \le m \le 1000 \$

输入描述:

输入共有M行

第一行输入一个数M表示有多少组测试数据，

接着有M行，每一行都输入一个 N 表示深渊的台阶数

输出描述:

输出可能的爬出深渊的方式

示例1

输入

输出

备注:

为了防止溢出，可将输出对10^9 + 3取模

算法知识视频讲解

tuweilong

/*
动态规划。类似于跳台阶。
用递归会超时。
取模防止溢出。
*/
import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int[] dp = new int[1001];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= 1000; i++) {
            int tmp = 1;
            while (tmp <= i) {
                dp[i] += dp[i - tmp];
                tmp *= 2;
                dp[i] %= 1000000000 + 3;
            }
        }
        while (T-- > 0) {
            int n = in.nextInt();
            System.out.println(dp[n]);
        }
    }
}

发表于 2019-06-28 11:07:14 回复(1)

Python

ElonB

"""
台阶问题考虑动态规划
每次仅可往上爬2的整数次幂个台阶(1、2、4、....)
当前台阶方法数 = 所有一次可到达当前台阶方法数的和
dp[n] = dp[n-1]+dp[n-2]+dp[n-4]+... ( n-t>=0,dp[0]=1 )
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    m = int(input().strip())
    mod = 1000000003
    dp = [0] * 1001
    dp[0] = 1
    for i in range(1, 1001):
        t = 1
        while t <= i:
            dp[i] += dp[i - t]
            dp[i] %= mod
            t = t * 2
    for _ in range(m):
        n = int(input().strip())
        print(dp[n])

发表于 2019-07-05 13:24:48 回复(7)

C/C++

江湖再见！

动态规划！

f(0) = 1; f(1) = 1; f(2) = 2; f(3) = 3; f(4) = 6……

这里与跳台阶每次只能选择跳一格或者两格的题目很类似。

从后往前考虑，台阶为n时，第一次可以跳2的指数个台阶，总共有1，2，4，8……k(k小于n)种跳法，剩下的n - k个台阶为台阶为n-k的跳法，可以得到下式：

f(n) = f(n-1) + f(n - 2) + f(n - 4) +... + f(n - k)

递归时将过程值保存，因为当计算f(5) = f(4) + f(3) + f(1)时，f(3)又要计算一遍，时间复杂度会爆表。

#include <iostream>
#include <algorithm>
using namespace std;

long Result[10001] = {0}; //存放各个n对应的结果


long NumOption(int n)
{
	long res = 0;
	if (n == 0) Result[0] = 1;
	if (n == 1) Result[1] = 1;
	if (n == 2) Result[2] = 2;
	int step = 0;
	if (Result[n] != 0) return Result[n]; // 若结果里已经有值，直接取出不用递归
	while (true)
	{
		if (n - pow(2, step) < 0) break; // 循环结束
		res += NumOption(n - pow(2, step));
		step++;
	}
	Result[n] = res % (1000000003);
	return Result[n];
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int in;
		cin>>in;
		long res = NumOption(in);
		cout << res << endl;
	}
	return 0;
}

编辑于 2020-04-01 10:09:49 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m,n[1001],res[1001];
    cin>>m;
    for(int i=0;i<m;i++)
        cin>>n[i];
    vector<int> p = {1,2,4,8,16,32,64,128,256,512};
    vector<long long> dp(1001,0);
    dp[0] = 1;
    for (int i = 1; i < dp.size();i++)
    {
        for (int j = 0; j < p.size();j++)
        {
            if (i >= p[j])
            {
                dp[i] = dp[i] + dp[i - p[j]];
                dp[i] %= 1000000003LL;
            }
        }
    }
    for(int i=0;i<m;i++)
        cout<<dp[n[i]]<<endl;
    return 0;
}

发表于 2019-06-30 14:53:04 回复(1)

C/C++

nbgao

	
		
		
			#include <bits/stdc++.h>
		

		
			using namespace std;
		

		
			const int MOD = 1e9+3;
		

		
			int main(){
		

		
			int M, N;
		

		
			int a[1001] = {1, 1};
		

		
			for(int i=2; i<=1000; i++){
		

		
			int p = 1;
		

		
			while(p<=i){
		

		
			a[i] = (a[i]+a[i-p])%MOD;
		

		
			p <<= 1;
		

		
			}
		

		
			}
		

		
			cin>>M;
		

		
			while(M--){
		

		
			cin>>N;
		

		
			cout<<a[N]<<endl;
		

		
			}
		

		
			return 0;
		

		
			}

编辑于 2019-07-06 20:19:35 回复(3)

C/C++

昔遥暮云

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    long long dp[1001]={0};
    dp[1]=dp[0]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=i;j<<=1)
            dp[i]+=dp[i-j];
        dp[i]%=1000000000 + 3;
    }
    cin>>n;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        cout<<dp[t]<<endl;
    }
    return 0;
}

发表于 2019-10-19 10:28:57 回复(0)

FEICHAI

#include<iostream>

#include<vector>

usingnamespacestd;

intmain()

{

intM;

cin>>M;

vector<int>***(10001,0);

***[0]=1;

intsub[]={1,2,4,8,16,32,64,128,256,512};

for(inti=0;i<1001;i++)

{

for(intj=0;j<10&&i>=sub[j];j++)

{

***[i]+=***[i-sub[j]];

***[i]%=1000000003;

}

intN=0;

for(inti=0;i<M;i++)

{

cin>>N;

cout<<***[N]<<endl;

}

return0;

}

发表于 2019-08-09 12:39:14 回复(0)

正在卷的三文鱼很讨厌吃香菜

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int M=sc.nextInt();
        int[] nums=new int[M];
        int max=0;
        for(int i=0;i<M;i++){
            int num=sc.nextInt();
            nums[i]=num;
            max=Math.max(max,num);
        }
        int[] dp=new int[max+1];
        dp[0]=1;
        for(int i=1;i<=max;i++){
            for(int j=0;i-(int)Math.pow(2,j)>=0;j++){
                dp[i]+=dp[i-(int)Math.pow(2,j)];
                //经验，可以在每次都取MOD，效果等同于最后取MOD，
                        //好处是能够防止溢出
                dp[i]%=1000000003;
            }
        }
        for(int i=0;i<M;i++){
            System.out.println(dp[nums[i]]);
        }
    }
}

发表于 2019-08-05 11:53:43 回复(0)

lentolove

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Solution4_魔法深渊 {

    final static int MOD = 1000000003;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(bf.readLine());
        int[] ans = new int[m];
        //保存最大那个数字 求得dp[max],直接在根据输入打印dp中对应的值
        int max = 0;
        for (int i = 0; i < m; i++) {
            int a = Integer.parseInt(bf.readLine());
            if (max<a) max = a;
            ans[i] = a;
        }
        int[] dp = jump(max);
        for (int i = 0; i < m; i++) {
            System.out.println(dp[ans[i]]);
        }

    }

    private static int[] jump(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j *= 2) {
                dp[i] += dp[i - j];
                dp[i] = dp[i] % MOD;
            }
        }
        return dp;
    }
}

发表于 2019-08-03 16:50:25 回复(0)

天地芳

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main(){
int n;
cin>>n;
long long a[1001]={0};
int b[10]={1,2,4,8,16,32,64,128,256,512};

a[0]=1;
a[1]=1;

for(int k=2;k<=1000;k++){
int l=0;
while(b[l]<=k){
a[k]=(a[k]+a[k-b[l]])%(1000000003);
l++;
}
}
int m;
for(int i=0;i<n;i++){
cin>>m;
cout<<a[m]<<endl;
}

}

发表于 2019-07-23 21:15:31 回复(1)

weekingqi

第6个台阶可以从2,4,5一次性到达，把dp[2],dp[3],dp[4],dp[5]求和即可

第1000个台阶可以从488(1000-512),744（1000-256）...999一次性到达，把dp[488]+...+dp[999]求和即可

https://blog.csdn.net/jxq0816/article/details/83934641

编辑于 2018-11-11 00:41:31 回复(0)

FlushHip

详细解析：
https://blog.csdn.net/FlushHip/article/details/83822873

发表于 2018-11-07 15:48:18 回复(0)

王子的诱惑

#coding=utf-8
def stair(m):#动态规划
    import math #导入对数哈函数
    re=[]#实现记忆
    for n in range(m+1):#从0~m进行计算
        if n==0:#边界条件
            re.append(1)
        elif n==1:
            re.append(1)
        else:
            d,s=int(math.log(n,2)),0#找到最接近的2**i，如n=5时，d=2
            for i in range(d+1):
                s+=re[n-2**i]#re[n]=re[n-2**i]+re[n-2**(i-1)]+.....+re[n-2**0]
            re.append(s)
    return re[-1]
while 1:
    try:
        n=int(input())
        for i in range(n):
            print(stair(int(input()))%1000000003)#防止溢而取模
    except:
        break

发表于 2020-08-17 12:14:36 回复(0)

原反补移码

#include<iostream>
(720)#include<vector>

using namespace std;

int main(void){
    int n;
    cin>>n;
    int stepNum;
    vector<int> dp(10001, 0);
    dp[1] = 1;
    dp[0] = 1;
    for (int i = 2; i <= 1000; i++){
        int Ex = 1;
        while (Ex <= i){
            dp[i] = (dp[i] + dp[i - Ex]) % (1000000000 + 3);
            Ex *= 2;
        }
    }
    for (int i = 0; i < n; i++){
        cin>>stepNum;
        cout<<dp[stepNum]<<endl;
    }
    return 0;
}

发表于 2020-05-02 17:58:59 回复(0)

hibari1015

对斐波那契数列进行推广即可

n=int(input())
def find(n):
    dp=[1]
    for i in range(1,n+1):
        s=0
        for j in range(n):
            if 2**j<=i:
                s+=dp[i-2**j]
            else:break
        dp.append(s)
    return dp[-1]
for i in range(n):
    print(find(int(input()))%(10**9 + 3))

发表于 2020-04-24 10:14:16 回复(0)

牛客8918761号

import math
M = int(input())
mi = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
mod = 1000000003
for i in range(M):
    n = int(input())
    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1
    for ni in range(2, n+1):
        end = int(math.log(ni, 2))
        for j in range(0, end+1):
            dp[ni] += dp[ni-mi[j]]
        dp[ni] %= mod
    print(dp[n])

发表于 2020-04-22 21:21:19 回复(0)

G^J

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt();
for(int i=0;i<m;i++) {
int n = in.nextInt();
System.out.println(ans(n));
}
}

private static long ans(int n) {
if(n == 1) {
return 1;
}
long[] dp = new long[n+1];
dp[1] = 1;
dp[0] = 0;
for(int i=2;i<=n;i++) {
long sum = ((i&(i-1))==0) ? 1 : 0;
for(int j=i-1;j>=1;j--) {
if(((i-j)&(i-j-1))==0) {
sum+=dp[j];
sum%=1000000003;
}
}
dp[i] = sum;
}
return dp[n];
}
}

发表于 2020-03-11 01:09:32 回复(0)

远征的梦想

完全背包问题，不过一定要注意溢出(真的是防不胜防)😥

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int M = Integer.parseInt(sc.nextLine());
        for(int i = 0;i<M;i++){
            int N = Integer.parseInt(sc.nextLine());
            long[] dp = new long[N+1];
            dp[0] = 1;
            for(int j = 1;j<=N;j++){
                for(int step : generateSteps(N)){
                    if(j >= step){
                        dp[j] = dp[j]+dp[j-step];
                        dp[j] %= 1000000003;
                    }
                }
            }
            long res = dp[N] % 1000000003;
            System.out.println(res);
         }
    }
    
    private static List<Integer> generateSteps(int N){
        List<Integer> steps = new ArrayList<>();
        int step = 1;
        while(N > 0){
            steps.add(step);
            N -= step;
            step *= 2;
        }
        return steps;
    }
}

发表于 2020-02-27 21:42:10 回复(0)

winkerwin

没有AC的注意一下取模，我就卡在这里了

发表于 2020-02-24 19:24:08 回复(0)

RichardLee0

#include<iostream>
using namespace std;

int dps(int i, int dp[]){
    if(dp[i]!=0) return dp[i];

    /*//法三，不知为何错误
    for(int j=i/2*2;j>=1;j/=2){
        dp[i] += dps(i-j, dp);
        dp[i] %= 1000000003;
    }*/
    
    //法二
    for(int j=1;j<=i;j*=2){
        dp[i] += dps(i-j, dp);
        dp[i] %= 1000000003;
    }
    return dp[i];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m,n;
    int dp[1001] = {0};
    dp[0]=1;dp[1]=1;
    /*//法一
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=i;j*=2){
            dp[i] += dp[i-j];
            dp[i] %= 1000000003;    //防止溢出
        }
    }*/
    cin>>m;
    while(m--){
        cin>>n;        
        //cout<<dp[n]<<endl; //法一
        cout<<dps(n, dp)<<endl;
    }
    return 0;
}

递归是自上而下，还是自下而上快？

发表于 2020-01-29 00:25:02 回复(0)

提交观点

问题信息

动态规划快手算法工程师 2019

上传者：小小

难度：

37条回答 88收藏 9795浏览

通过挑战的用户

查看代码

Delicacies

2022-09-13 16:49:39
啊展是啊这

2022-09-05 21:14:14
ぃる

2022-08-31 22:45:51
一世白纸

2022-08-28 17:43:03
前端学习中

2022-08-27 18:37:10

魔法深渊

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题