动态规划的思想

它的思想就是把一个大的问题进行拆分，细分成一个个小的子问题，且能够从这些小的子问题的解当中推导出原问题的解。同时还需要满足以下两个重要性质才能进行动态规划
最优子结构性: 既所拆分的子问题的解是最优解。

子问题重叠性质: 既在求解的过程当中，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率

1.斐波拉契数列

  • 计算斐波那契数列：斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…这个数列从第3项开始，每一项都等于前两项之和。

JS
function FibonacciPull(num) {
if (num === 1 || num === 2) {
return 1
}

const val = [];

for (let i = 0; i < num; i++) {
if (i === 0 || i === 1) {
val[i] = 1
} else {
val[i] = val[i - 1] + val[i - 2];
}
}

console.log(val[num - 1]);
return val[num - 1];
}

FibonacciPull(5)
结果
image.png

2.**爬梯子问题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：输入： 2 输出： 2
解释： 有两种方法可以爬到楼顶。
a、1 阶 + 1 阶 b、2 阶
示例 2：输入： 3 输出： 3
解释： 有三种方法可以爬到楼顶。
a、1 阶 + 1 阶 + 1 阶 b、1 阶 + 2 阶 c、2 阶 + 1 阶
走1阶台阶只有一种走法，但是走2阶台阶有两种走法（如示例1），如果n是双数，我们可以凑成m个2级台阶，每个m都有两种走法，如果n是单数，那么我们可以凑成m个2级台阶加上一个1级台阶，这样就似乎于一个排列组合题目了，但是开销貌似比较大。**

JS
function ClimbTheLabber(num) {
const val = [];

if (num === 1) {
return 1;
} else if (num === 2) {
return 2;
} else {
for (let i = 0; i < num; i++) {
if (i === 0) {
val[0] = 1;
} else if (i === 1) {
val[1] = 2;
} else {
val[i] = val[i - 1] + val[i - 2];
}
}
}

console.log(val[num - 1])
return val[num - 1];
}

ClimbTheLabber(5)

结果：
image.png

3.**所有路径问题
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？**
function AllPathProblems(m, n) {
if (m === 0 || n === 0) {
return 0;
}

if (m === 1 || n === 1) {
return 1;
}

const val = {};

for(let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0) {
val[${i}*${j}] = 1;
} else if (j === 0) {
val[${i}*${j}] = 1;
} else {
val[${i}*${j}] = val[${i-1}*${j}] + val[${i}*${j-1}]
}
}
}
console.log(val[${m-1}*${n-1}])
return val[${m-1}*${n-1}]
}

AllPathProblems(7, 3);

结果为：
image.png