动态规划(一)

本文为学习代码随想录时所做的笔记，仅供学习参考，不做任何商业用途，若有侵权，请联系删除。

动态规划(一)

动态规划理论基础

什么是动态规划

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

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

动态规划的解题步骤

  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

动态规划应该如何debug

找问题的最好方式就是把dp数组打印出来，看是否和自己的思路相一致。

斐波那契数

509. 斐波那契数 - 力扣（Leetcode）

  1. 确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数数值是dp[i]

  1. 确定递推公式

\[dp[i] = dp[i-1] + dp[i-1]\]

  1. dp数组如何初始化
1
2
dp[0] = 0;
dp[1] = 1;
  1. 确定遍历顺序

从前向后遍历

  1. 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

初始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(N+1);
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= N; i ++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        
        return dp[N];
    }
};

优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i ++) {
            int sum = dp[0] + dp[1];
            dp [0] = dp[1];
            dp[1] = sum;
        }
        
        return dp[1];
    }
};

爬楼梯

70. 爬楼梯 - 力扣（Leetcode）

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

  1. 确定dp数组奇迹含义

dp[i]:爬到第i层楼梯，有dp[i]种方法。

  1. 确定递推公式

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！

所以dp[i] = dp[i - 1] + dp[i - 2] 。

  1. dp数组如何初始化

不考虑dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。

  1. 确定遍历顺序

从前向后遍历

  1. 举例推导dp数组

举例当n为5的时候，dp table（dp数组）应该是这样的

此时大家应该发现了，这不就是斐波那契数列么！

初始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i ++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        
        return dp[n];
    }
};

优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};

拓展

这道题目还可以继续深化，就是一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。

这又有难度了，这其实是一个完全背包问题，但力扣上没有这种题目，所以后续我在讲解背包问题的时候，今天这道题还会从背包问题的角度上来再讲一遍。 如果想提前看一下，可以看这篇:70.爬楼梯完全背包版本

使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（Leetcode）

  1. 确定dp数组以及下标的含义

dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。

  1. 确定递推公式

可以有两个途径得到dp[i]，一个是dp[i-1]，一个是dp[i-2]

dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])

  1. dp数组如何初始化

dp[0]=0,dp[1]=0

  1. 确定遍历顺序

从前到后遍历cost数组

  1. 举例推导dp数组

初始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1);
        dp[0] = 0;
        dp[1] = 0;
        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()];
    }
};

优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = 0;
        int dp1 = 0;
        for (int i = 2; i <= cost.size(); i ++) {
            int dpi = min(dp1+cost[i-1], dp0+cost[i-2]);
            dp0 = dp1;
            dp1 = dpi;
        }
        
        return dpi;
    }
};

不同路径

62. 不同路径 - 力扣（Leetcode）

机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点！

深搜

1
2
3
4
5
6
7
8
9
10
11
12
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);
    }
};

动态规划

  1. 确定dp数组以及其下标的含义
1
dp[i][j]，表示从（0，0）出发，到（i,j）有dp[i][j]条不同的路径
  1. 确定递推公式
1
dp[i][j] = dp[i-1][j] + dp[i][j-1]
  1. dp数组的初始化
1
2
for (int i = 0; i < m; i ++) dp[i][0] = 1;
for (int j = 0; j < n; j ++) dp[0][j] = 1;
  1. 确定遍历顺序

从左到右一层层遍历

  1. 举例推导dp数组

初始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
	int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i ++) dp[i][0] = 1;
        for (int j = 0; j < n; j ++) dp[0][j] = 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];
    }
};

优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n);
        for (int i = 0; i < n; i ++) dp[i] = 1;
        for (int j = 1; j < m; j ++) {
            for (int i = 1; i < n; i ++) {
                dp[i] += dp[i-1];
            }
        }
        
        return dp[n-1];
    }
};

数论方法

在这个图中，可以看出一共m，n的话，无论怎么走，走到终点都需要 m + n - 2 步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
    }
};
算法
#动态规划
动态规划(一)
https://www.spacezxy.top/2023/04/02/Algorithm/algorithm-11/
作者
Xavier ZXY
发布于
2023年4月2日
许可协议