C++算法学习心得八.动态规划算法（1）

本文介绍: 动态规划理论基础：动态规划是一个问题有很多子问题时候使用非常适合，其是由上一个状态推到出来的，贪心算法是由局部最优推出全局最优，动态规划五部曲，定义dp数组，初始化，遍历顺序，递推公式，打印。

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

对于动态规划问题，拆解为如下五步曲，

一些情况是递推公式决定了dp数组要如何初始化

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的。

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果

dp[0] = 0;
dp[1] = 1;

class Solution {
public:
    int fib(int n) {
        if(n<=1)return n;//
        vector<int>dp(n+1);//定义一个动态规划数组，含义是第i个斐波那契数
        dp[0] = 0;//初始值设定
        dp[1] = 1;
        //遍历顺序，从前向后遍历
        for(int i = 2;i <= n;i++){
            dp[i] = dp[i - 1] + dp[i-2];//递推公式
        }
        return dp[n];//求第n个斐波那契数
    }
};

class Solution {
public:
    int fib(int n) {
        if(n < 2)return n;
        return fib(n - 1) + fib(n - 2);
    }
};

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 1)return n; 因为下面直接对dp[2]操作了，防止空指针
        vector<int>dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        // 注意i是从3开始的
        for(int i = 3;i <= n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int>dp(cost.size()+1);//定义数组
        dp[0] = 0;//初始化
        dp[1] = 0;
        //从i = 2从前向后遍历
        for(int i = 2;i <= cost.size();i++){
            dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);//递推公式
        }
        return dp[cost.size()];
    }
};

class Solution {
private:
    int dfs(int i, int j, int m, int n) {
        if (i > m || j > n) return 0; // 越界了
        if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
public:
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m,vector<int>(n,0));//定义dp二维数组，大小为mxn
        for(int i = 0;i < m;i++)dp[i][0] = 1;//首先对最上面一行进行初始化为1
        for(int j = 0;j < n;j++)dp[0][j] = 1;//对最右边的一列初始化为1
        //我们沿着从左到右，从上到下遍历的顺序进行遍历
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];//递推公式
            }
        }
        return dp[m-1][n-1];//返回值
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1; // 分子
        int denominator = m - 1; // 分母
        int count = m - 1;
        int t = m + n - 2;
        while (count--) {
            numerator *= (t--);
            while (denominator != 0 && numerator % denominator == 0) {
                numerator /= denominator;
                denominator--;
            }
        }
        return numerator;
    }
};