求快手算法A卷爬楼梯的题解

#include<iostream> #include<vector> using namespace std; const int mod = 1000000003; int main(){ int M, n; cin>>M; while(M--){ cin>>n; vector<int> dp(n+1, 0); dp[0] = 1; for(int i = 1; i <= n; i++){ int t = 1; while(i - t >= 0){ dp[i] = (dp[i]%mod + dp[i-t]%mod)%mod; t *= 2; } } cout<<dp[n]<<endl; } }

#include <bits/stdc++.h> using namespace std; uint64_t stage[1024]; int main() {     int T; cin >> T;     for (int i = 0; i < T; i++) {         int N; cin >> N;         memset(stage, 0, sizeof(stage));         stage[0] = 1;         stage[1] = 1;         stage[2] = 2;         for (int k = 3; k <= N; k++) {             int t = 1;             while (k - t >= 0) {                 stage[k] = (stage[k] % 1000000003L + stage[k - t] % 1000000003L) % 1000000003L;                 t <<= 1;             }         }         cout << stage[N] << endl;     }     return 0; }

DFS 这道题肯定超时，其实这个题目和 1，2 爬楼梯是一个思路。即你要走到第 N 个楼梯 你要不是从 N-1, N-2, N-4, N-8 ... 这些楼梯上来的，所以 f(N) = sum(f(N-2^k)) k=0,1,2,3 ...  然后从小往大推就行  

问题出在最后一层台阶不是终点,还需要再上一个台阶,所以要再来一次Math.min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2]) import java.util.Scanner; public class q2 { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); String s = scanner.next(); String[] strs = s.split(","); int n = strs.length; int[] cost = new int[n]; for (int i = 0; i < n; i++) { cost[i] = Integer.parseInt(strs[i]); } int dp[] = new int[n]; dp[0] = 0; dp[1] = 0; for (int i = 2; i < n; i++) { dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } System.out.print(Math.min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])); } }

求机器人分菜的代码或者思路 ###########2，以2的次幂方式进行跳楼梯 a=[1,1] i=2 while(i<=1000):     x=0     temp=0     while((i-2**x)>=0):         temp=temp+a[i-2**x]         x=x+1     a.append(temp)     i=i+1 m=int(input()) in_list=[] for i in range(m):     num=(int(input()))     print((a[num])%(10**9+3))

#include<iostream> #include<cmath> using namespace std; long long int f[1001] = {0}; long long int do_calc(int n) {     if (n == 0)         {         f[0] = 1;         return f[0];     }     else if (n == 1)      {         f[1] = 1;         return f[1];     }     else     {         if (f[n] != 0)         {             f[n] %= (long long int)pow(10,9)+3;             return f[n];         }         int item = (long long int)(log(n) / log(2)) + 1;            for (int k = 0; k < item; k++)         {             f[n] += do_calc(n - (1 << k));         }         f[n] %= (long long int)pow(10,9)+3;            return f[n];     } } int main() {     int M;     cin >> M;     while (M > 0)     {         int n;         cin >> n;         cout << do_calc(n) << endl;         M--;     }     return 0; }

dp[i]=Matn.min(dp[i-1]，dp[i-2])＋cost[i] n>＝2 Math.min（cost[0]，cost[1]） n<2

def foo(n): dp = [0] * (n + 1) dp[0] = 1 for i in range(1, n + 1): j = 1 while j <= n: if i < j: break dp[i] = dp[i] + dp[i - j] j = j * 2 return dp[n] % 1000000003 N = int(input()) for i in range(N): n = int(input()) print(foo(n))