嗯是爬楼梯，刚看题没有什么思路，举几个栗子来看看规律，找到规律后使用规律来阶梯。
题干
[力扣-爬楼梯]
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意： 给定 n 是一个正整数。
示例 1：
1
2
3
4
5
| 输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
|
示例 2：
1
2
3
4
5
6
| 输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
|
动态规划
思路
观察结果：
n=1 时，1 种；
n=2 时，2 种；
n=3 时，3 种；
n=4 时，5 种；
…
不难发现，第 n 次的结果是 n-1 次与 n-2 次之和。
当然你写递归也行，但是那样总是有很多重复计算，不如来动态规划，存储之前算过的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution
{
public int ClimbStairs(int n)
{
var table = new int[n - 1]; // 创建表
if (n <= 3) return n; // i <= 3时，返回相应结果即可
// 初始化表
table[1] = 2;
table[2] = 3;
// 计算前两次的值并存储
for (int i = 3; i < n - 1; i++)
{
table[i] = table[i - 1] + table[i - 2];
}
return table[n - 2] + table[n - 3];
}
}
|
排列组合脑瘫算法
思路
来举例子吧：
n=1 时，1 种：
n=2 时，1+1 种：
n=3 时，2+1 种：
n=4 时，1+3+1 种：
1
2
3
| 2 2
2 1 1 // C(3,1)
1 1 1 1
|
n=5 时，`` 种：
1
2
3
| 2 2 1 // C(3,2)
2 1 1 1 // C(4,1)
1 1 1 1 1
|
好，找到规律了：
- 判断奇数还是偶数，是奇数 result + 1，是偶数 result + 2；
- y = (x - 1) / 2；
- i 循环 y 次，result + C(x - i, i)， i++
超时，然后优化计算组合数部分，使用 HashSet<T> 来存储分子然后相消。
总之想这个挺有趣的呢。
最终代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| public class Solution
{
public static void Main()
{
var t = new Solution();
Console.WriteLine(t.ClimbStairs(44));
}
public int ClimbStairs(int n)
{
var result = IsEven(n) ? 2 : 1; // 奇数偶数预先加值
var cnt = (n - 1) >> 1; // 循环组合次数
for (var i = 1; i <= cnt; i++)
result += Combine(i, n - i); // 计算组合值
return result;
}
/// <summary>
/// 是否为奇数
/// </summary>
/// <param name="num">数字</param>
/// <returns>是否为奇数</returns>
private static bool IsEven(int num)
=> (num & 1) == 0;
/// <summary>
/// 是否为奇数
/// </summary>
/// <param name="num">数字</param>
/// <returns>是否为奇数</returns>
private static bool IsEven(long num)
=> (num & 1) == 0;
/// <summary>
/// 计算阶乘
/// </summary>
/// <param name="x">阶数</param>
/// <returns>x!</returns>
private long Factorial(long x)
=> x <= 1 ? 1 : x * Factorial(x - 1);
/// <summary>
/// 组合
/// </summary>
/// <param name="m">取出元素的个数</param>
/// <param name="n">元素总个数</param>
/// <returns></returns>
private int Combine(int m, int n)
{
// 分子值
long moleculeValue = 1;
long denominatorValue;
// 分子的集合
var moleculesList = new HashSet<int>();
for (var i = 1; i <= n; i++)
{
moleculesList.Add(i);
}
// 分母的集合
var denominatorsList = new LinkedList<int>();
// 选取较少的一项进行计算
int denominatorCnt;
var o = n - m;
// 分母值
if (o > m)
{
denominatorValue = Factorial(m);
denominatorCnt = o;
}
else
{
denominatorValue = Factorial(o);
denominatorCnt = m;
}
// 进行分子分母相消
for (var i = 1; i <= denominatorCnt; i++)
{
if (moleculesList.Contains(i))
{
moleculesList.Remove(i);
}
else
{
denominatorsList.AddLast(i);
}
}
// 计算分母值
foreach (var val in denominatorsList)
{
denominatorValue *= val;
}
// 计算分子值
foreach (var val in moleculesList)
{
if (IsEven(val) && IsEven(denominatorValue))
{
denominatorValue >>= 1;
moleculeValue *= (val >> 1);
}
else
{
moleculeValue *= val;
}
}
return (int)(moleculeValue / denominatorValue);
}
}
|