算法设计思想——动态规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法设计思想——动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划（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 <iostream>
#include <vector>
using namespace std;

class MyMethod {
public:
    int clbStairs(int n){
        if (n == 1) return 1;
        if (n == 2) return 2;
        vector<int> st(n+1);
        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 <iostream>
#include <vector>
using namespace std;

class MyMethod {
public:
    int clbStairs(int n){
        if (n == 1) return 1;
        if (n == 2) return 2;
        vector<int> st(n+1);
        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）：