C++ 一维动态规划

**一维动态规划**

一维动态规划是一种常见的算法设计模式，用于解决具有最优子结构的问题。在这种情况下，我们将使用 C++语言来实现一个简单的例子。

###什么是动态规划？

动态规划是一种通过分解大问题为小问题，并以递归方式求解这些小问题的方法。它通常涉及以下步骤：

1. **定义状态**: 确定问题中需要考虑的变量或状态。
2. **建立转移方程**: 根据当前状态和历史信息计算下一个状态的值。
3. **使用记忆化**:保存已经计算过的状态，以避免重复计算。

### 一维动态规划例子：斐波那契数列斐波那契数列是一个经典的动态规划问题。它定义为：

* F(0) =0* F(1) =1* F(n) = F(n-1) + F(n-2)

我们将使用 C++ 来实现一个一维动态规划算法来计算斐波那契数列。

cpp#include <iostream>
using namespace std;

// 定义状态：斐波那契数列的值int fibonacci(int n, int memo[]) {
 // 如果已经计算过，则直接返回结果 if (memo[n] != -1) return memo[n];

 // 递归计算斐波那契数列的值 if (n ==0) return0;
 else if (n ==1) return1;
 else {
 int result = fibonacci(n-1, memo) + fibonacci(n-2, memo);
 memo[n] = result; // 记忆化结果 return result;
 }
}

int main() {
 int n =10; // 计算斐波那契数列的前10 项 int memo[11]; // 使用一维数组来存储计算过的状态 for (int i =0; i <= n; i++) {
 memo[i] = -1; // 初始化记忆化数组 }

 cout << "斐波那契数列前10 项：" << endl;
 for (int i =0; i <= n; i++) {
 cout << fibonacci(i, memo) << " ";
 }
 return0;
}