新爬楼梯(一步登天)(列出具体爬法)

LeetCode

原题爬楼梯，请直接参考leetcode-爬楼梯

建议先阅读下leetcode原题，也可以直接往下看该题的解题思路

我在其基础上做了一个抽象，即使用任意步数，爬任意高的楼梯，爬到最后一层有多少种爬法

推导出转移方程

假设，爬楼梯，可以1步、2步、3步。。。。n步
楼梯总高为m，那么爬到m层，所有爬法的方程如下

1
2
3
f(m) = f(m-1) + f(m-2) + f(m-3) + ... + f(m-n)

即：需要爬到m层的爬法，由如下的层数的爬法累加得到

先进行数学归纳法

假设步骤只有1步、2步、3步

看如下数学归纳法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// f函数的参数，表示当前爬的楼层数
// 值表示：爬到该层数，所有的爬法数
f(0) = 0; 
// f(1) = f(1-1) + 1
f(1) = f(0) + 1; // 这里加1的目的，表示，当前可以一步爬上去，看如下说明，即可明白

// f(2) = f(2-1) + f(2-2) + 1;
f(2) = f(1) + f(0) + 1; // 支持一次爬2步，那么也需要加上一步登天 +1

// f(3) = f(3-1) + f(3-2) + f(3-3) + 1
f(3) = f(2) + f(1) + f(0) + 1; // 同样支持一次爬3步，一步登天  +1 

// f(4) = f(4-1) + f(4-2) + f(4-3)
// f(5) = f(5-1) + f(5-2) + f(5-3)

...

f(5) = f(4) + f(3) + f(2) // 没有一步登天，即计算完毕

所以，我们看到，这里存在一个一步登天的变量，需要另外加上去

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const newClimbStairs = (total, steps) => {
  const f = {};
  // 初始状态定位0，即没有爬楼
  f[0] = 0;

  for (let i = 1; i <= total; i++) {
    f[i] = 0;
    for (let j = 0; j < steps.length; j++) {
      if (i > steps[j]) {
        // 只要当前楼层大于当前步数，就进行累加
        f[i] = f[i - steps[j]] + f[i];
      }
      // 这里是一步登天的判断
      if (i === steps[j]) {
        // 如果发现当前楼层支持一步登天，就再加上1
        f[i] = f[i] + 1;
      }
    }
  }
  return f[total];
};

测试结果

多了一个一步登天的“爬50步”，所有步骤也仅仅多了一步

1
2
3
4
console.log(newClimbStairs(50, [1, 2]));
console.log(newClimbStairs(50, [1, 2, 50]));
// 20365011074
// 20365011075

计算爬法步骤

我们已经基于动态规划的方式，计算出爬楼梯的爬法步骤，但是并不知道具体怎么爬

那么接下来，这个算法，将列出，这些具体的爬法是什么

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
// 将数组的值进行累加
const arrAll = (a) => {
  let sum = 0;
  for (let i = 0; i < a.length; i++) {
    sum += a[i];
  }
  return sum;
};

const start = (steps, target) => {
  const res = [];

  for (let i = 0; i < steps.length; i++) {
    res.push([steps[i]]);
  }

  // 把每一层都走一遍
  for (let i = 1; i <= target; i++) {
    // 给走过的层数，添加当前这一层需要走的步
    for (let j = 0; j < res.length; j++) {
      // 添加步数
      for (let m = 0; m < steps.length; m++) {
        const value = [...res[j], steps[m]];
        // 步数操作总层数，就不再进行计算了
        if (arrAll(value) <= target) {
          res.push(value);
        }
      }
    }
  }

  const result = [];

  for (let i = 0; i < res.length; i++) {
    if (arrAll(res[i]) === target) {
      result.push(res[i].join("-"));
    }
  }

  return Array.from(new Set(result));
};
console.log(start([1, 2, 3], 4));
// 输出
/**
[
  '1-3',     '2-2',
  '3-1',     '1-1-2',
  '1-2-1',   '2-1-1',
  '1-1-1-1'
]
总计7种爬法
*/
LeetCode