爬楼梯-力扣70 动态规划
Gaein nidb Lv5

嗯是爬楼梯,刚看题没有什么思路,举几个栗子来看看规律,找到规律后使用规律来阶梯。

题干

[力扣-爬楼梯]

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意: 给定 n 是一个正整数。
示例 1:

1
2
3
4
5
6
7
输入: 2  
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
```
示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶
    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

    ## 动态规划

    #### 思路

    观察结果:

    `n=1` 时,`1` 种;
    `n=2` 时,`2` 种;
    `n=3` 时,`3` 种;
    `n=4` 时,`5` 种;
    ...

    不难发现,第 `n` 次的结果是 `n-1` 次与 `n-2` 次之和。

    当然你写递归也行,但是那样总是有很多重复计算,不如来动态规划,存储之前算过的:

    ```csharp
    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 种:

1
1

n=2 时,1+1 种:

1
2
2
1 1

n=3 时,2+1 种:

1
2
2 1     // C(2,1)
1 1 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

好,找到规律了:

  1. 判断奇数还是偶数,是奇数 result + 1,是偶数 result + 2;
  2. y = (x - 1) / 2;
  3. 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);
}
}