跳台阶动态规划c++

以下是跳台阶动态规划的C++代码实现：

#include <iostream>
using namespace std;

int jumpFloor(int number) {
    if (number <= 0) {
        return 0;
    } else if (number == 1) {
        return 1;
    } else if (number == 2) {
        return 2;
    } else {
        int a = 1, b = 2, c;
        for (int i = 3; i <= number; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

int main() {
    int n = 10;
    cout << "跳上" << n << "级台阶的跳法总数为：" << jumpFloor(n) << endl;
    return 0;
}

相关问题

青蛙跳台阶递归算法c++

以下是使用C++递归算法解决青蛙跳台阶问题的示例代码：

#include <iostream>
using namespace std;

int jumpFloor(int n) {
    if (n <= 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return jumpFloor(n - 1) + jumpFloor(n - 2);
    }
}

int main() {
    int n = 7;
    int result = jumpFloor(n);
    cout << "跳上 " << n << " 级台阶的跳法总数为：" << result << endl;
    return 0;
}

运行结果：

跳上 7 级台阶的跳法总数为：21

状态压缩动态规划c++

状态压缩动态规划是一种常用的算法，可以用来解决一些NP问题。在C++中，可以使用位运算来进行状态压缩，具体实现如下：

1. 定义状态压缩变量

int state = 0; // 定义一个整型变量来表示状态

2. 设置状态压缩位

state |= (1 << i); // 将第i位设置为1
state &= ~(1 << i); // 将第i位设置为0

3. 判断状态压缩位

if (state & (1 << i)) { // 判断第i位是否为1
    // do something
}

4. 动态规划

根据状态压缩的前提，定义合适的dp数组并找到状态转移方程，进行动态规划操作。

int dp[1 << n]; // 定义dp数组，n为状态压缩位数
for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
        if (i & (1 << j)) {
            dp[i] = max(dp[i], dp[i ^ (1 << j)] + a[j]);
        }
    }
}