动态规划（Dynamic Programming，简称DP)
是一种常见的算法设计方法，用于解决一类重叠子问题的优化问题。他的基本思想是将问题分解成多个重叠的子问题，递归求解，并将子问题的求解缓存起来，避免重复计算，从而得到问题的解。
动态规划通常适用于以下两个条件的问题： 1.重叠子问题：原问题可以分解为若干个子问题，子问题之间存在重叠部分，即某些问题的解在求解过程中被多次引用。
2.最优子结构：原问题的最优解可以由子问题的最优解推导得到，即原问题的最优解包含子问题的最优解。
动态规划算法的基本步骤如下：
定义状态：将原问题划分为若干个子问题，并定义状态表示子问题的解。定义状态转移方程：根据子问题之间的关系，建立子问题之间的递推关系式，即状态转移方程。初始化状态：确定初始化的值，即最简单的子问题的解。计算状态：按照状态转移方程，从简单的子问题开始递推，计算出所有子问题的解。求解原问题：根据子问题的解，求出原问题的解 。
动态规划算法的时间复杂度通常为或，取决于问题的规模和状态转移方程的复杂度。
下面来看例题：
假设你正在爬楼梯。需要n阶你才能到达楼顶。
每次你可以爬 1或 2 个台阶。那么一共有多少种不同的方法可以爬到楼顶呢？
下面以动态规划五部曲原则来进行构思：
定义状态：需要定义一个一维数组来记录不同楼层的状态，因此我们需要——确定St数组以及下标的含义 St[i]：爬到第i层，有St[i]种方法确定递推公式：首先如果是 st[i-1]，上 i-1 层楼梯，有 st[i-1] 种方法，那么再一步跳一个台阶就是 St[i]；如果是 St[i-2]，上 i-2 层楼梯，有 St[i-2] 种方法，那么再跳一步两个台阶就是St[i]，于是st[i] = st[i-1] + st[i-2]。St数组的初始化：我们需要考虑为St为0的情况，按照题干来理解，当楼层为0的时候，我们什么也不用做，于是i就为 0。有一个争议点就是：当St[0]应该为1的理由其实是因为dp[0] =1的话在递推的过程中 i 从 2 开始遍历才能执行下去，实际从题干出发，n是正整数，那么i也应该为为正整数，所以不需要讨论St[0]的初始化，我们直接从dp[1] = 1；dp[2] =2，然后从 i = 3开始递推。确定遍历顺序：由递推公式st[i] = st[i-1] + st[i-2]得到，遍历顺序从前向后举例推导St数组：当例如，我们n = 6时，st table如下：
没错，这其实就是斐波那契数列（Fibonacci sequence），五部曲分析完成后，我们的代码如下：
#include
#include
using namespace std;
class MyMethod {
public:
int clbStairs(int n){
if (n == 1) return 1;
if (n == 2) return 2;
vector
st[1] = 1;
st[2] = 2;
for (int i = 3; i <= n; i++){
st[i] = st[i-1] + st[i-2];
}
return st[n];
}
};
int main(){
int n = 6;
int ret = MyMethod().clbStairs(n);
cout << ret << endl;
return 0;
}
时间复杂度（time complexity）：
空间复杂度（space complexity）：
考虑到代码优化的话，我们用sum减少数据结构，使用常量来保存状态，代码如下：
#include
#include
using namespace std;
class MyMethod {
public:
int clbStairs(int n){
if (n == 1) return 1;
if (n == 2) return 2;
vector
st[1] = 1;
st[2] = 2;
for (int i = 3; i <= n; i++){
int sum = st[1] + st[2];
st[1] = st[2];
st[2] = sum;
}
return st[2];
}
};
int main(){
int n = 6;
int ret = MyMethod().clbStairs(n);
cout << ret << endl;
return 0;
}
时间复杂度（time complexity）：
空间复杂度（space complexity）：
总结
虽然这道题的实质是斐波那契数列，但理解到动态规划的程序设计思路其实没那么轻松，关键是能够迅速捕捉到这一概念，进行建模，按照动态规划五部曲的递推公式，逐步推导得到结果。
好文链接
您阅读本篇文章共花了：
发表评论