动态规划、递推
跳台阶
http://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
该题与斐波那契数列如出一辙，当前状态只与前两个状态有关，且为前两者之和。利用两个变量保存前两个状态来代替dp数组，可节省空间。 要跳上第n级台阶，要么从第n-1级台阶跳上去，要么从第n-2级台阶跳上去。故而，跳上第n级台阶的可选方案数目，为跳上第n-1级台阶的方案数目和跳上第n-2级台阶的之和。
class Solution {
public:
int jumpFloor(int number) {
if (number == 1)
return 1;
if (number == 2)
return 2;
int dp1 = 1;
int dp2 = 2, dpn = 2;
for (int i = 3; i <= number; i++) {
dpn = dp1 + dp2;
dp1 = dp2;
dp2 = dpn;
}
return dpn;
}
};
字节跳动三面396人在聊
投递字节跳动等公司9个岗位
查看21道真题和解析
腾讯公司福利 575人发布