几种走法

Problem description

从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？

Input format　

一个数N。1<=N<=1000。

Output format

一个整数，表示共有多少种走法。由于结果可能很大，你只需要输出这个答案mod 12345的值。

Algorithm design

搜索TLE/动态规划AC

Problem analysis

搜索TLE

一开始大脑短路没有思路就先写了搜索

发现好像挺难写

如果取起点为0，0，那么会出现负数的情况

所以还加了各种补丁，为数组设定象限

其实是一开始没有考虑好，直接取起点为1001,0就行了

说到底还是搜索不熟练

动规AC

O（n3）

题目中小蛮可以向左走也可以向右走非常的闹心

如果单纯地采用一维转移会有后效性，可能原地踏步

唯有向上走是很简单的，且每到达1个新的高度就无后效性

所以采用1个状态细分思想

设定高度h和步数n两个要素

Obviously,（h,n）可以由（h-1,n-1）向上1步的来

同时也可以由（h,n-j）向左或右转移而来

但是探究一下就能发现，小蛮在一定高度只能向左或右一个方向走

所以如果（h,n-j）是由某个点向左或向右走过来，一定会被重复

故只需要考虑（h,n-j）由一个点向上走过来的情况，即（h-1，n-j-1）

由上得：

O(n2)

很简单，O（n3）的前缀和

O(n)

每个点都可以由步数少1的点向上1步或者向左右中某一个方向1步得来

这样一定不会有重复，则opt[i]=2*opt[i-1]

但是其中“冤枉”了一些可以向左右两个方向延伸的点

他们都可以再走另一种方式

而可以向左右延伸的点必定是刚到达一个新高度的点

也就是opt[i-2]向上1步形成的节点

则opt[i]=2*opt[i-1]+opt[i-2];

难点：状态细分

【Source code】

 1 #include <bits/stdc++.h>
 2 #define lim 1010
 3 #define mo 12345
 4 
 5 using namespace std;
 6 
 7 int sum,ans,opt[lim][lim];
 8 /*
 9    sum即为总步数
10    ans即为总方案数
11    opt[h][n]意为走n步到达h高度的方案数
12 */
13 
14 void input()
15 {
16     freopen("problem3.in","r",stdin);
17     freopen("problem3.out","w",stdout);
18     cin>>sum;
19     return ;
20 }
21 //读入处理
22 
23 void operate()
24 {
25     opt[0][0]=1;
26     for(int i=1;i<=sum;i++)
27         opt[0][i]=2;
28     /*
29        初始化，不走当然是1种方案
30        在0级高度只能向1个方向走，当然是2种
31     */
32     for(int i=1;i<=sum;i++)
33     {
34         int wei=0;
35         for(int j=i;j<=sum;j++)
36         {
37             opt[i][j]=(opt[i-1][j-1]+wei)%mo;
38             wei+=2*opt[i-1][j-1];
39         }
40     }
41     /*
42        每个节点都可由2种方式延伸
43        1.由下方节点向上
44        2.由左右节点向右左延伸
45        为了规避重复，可以取左右节点的下方节点的方案总数，那么每个左右节点都可视作刚到达该高度
46        这里肯定可以用一个前缀和思想退成o（n2），先不用，测一下数据强度
47        竟然就ac了..
48        没关系还是要优化到最简
49     */
50 }
51 
52 void output()
53 {
54     for(int i=0;i<=sum;i++)
55         ans=(ans+opt[i][sum])%mo;
56     cout<<ans<<endl;
57     fclose(stdin);
58     fclose(stdout);
59     return ;
60 }
61 
62 int main()
63 {
64     input();
65     operate();
66     output();
67     return 0;
68 }

O(n2)

 1 #include <bits/stdc++.h>
 2 #define lim 1010
 3 #define mo 12345
 4 
 5 using namespace std;
 6 
 7 int sum,opt[lim];
 8 /*
 9    sum即为总步数
10    ans即为总方案数
11    opt[n]意为走n步的方案数
12 */
13 
14 void input()
15 {
16     freopen("problem3.in","r",stdin);
17     freopen("problem3.out","w",stdout);
18     cin>>sum;
19     return ;
20 }
21 //读入处理
22 
23 void operate()
24 {
25     opt[0]=1;
26     opt[1]=3;
27     for(int i=2;i<=sum;i++)
28         opt[i]=(2*opt[i-1]+opt[i-2])%mo;
29     return ;
30 }
31 
32 void output()
33 {
34     cout<<opt[sum]<<endl;
35     fclose(stdin);
36     fclose(stdout);
37     return ;
38 }
39 
40 int main()
41 {
42     input();
43     operate();
44     output();
45     return 0;
46 }

O(n)