动态规划开篇首章

未分类 1天前程序员胖胖胖虎阿

5 0 0

动态规划开篇首章

前言：

在计算机科学领域，动态规划（Dynamic Programming，简称DP）是解决最优化问题的关键手段。它通过把大问题分解成小问题来处理，能大幅降低计算复杂度，提升效率。无论是经典的背包问题，还是复杂的路径最短问题，动态规划都能给出简洁高效的解法。

本篇文章将引领你踏入动态规划的世界，从基础概念到实际应用，逐步揭开这一算法的神秘面纱。无论你是算法新手，还是渴望深入探究动态规划原理的开发者，本文都会为你提供清晰的思路和具体的示例。😊😊

1. 第 N 个泰波那契数（简单）

1. 题目链接

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

2. 解法（动态规划）

算法流程
1. 状态定义
此题可依题意直接定义状态：dp[i]代表第i个泰波那契数的值。
2. 状态转移方程
题目已明确给出：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
3. 初始化
由递推公式可知，i=0和i=1时无法推导，因为dp[-2]或dp[-1]无意义。题目已告知dp[0] = 0，dp[1] = dp[2] = 1，需提前初始化这些值。
4. 填表顺序
必然是“从左到右”进行。
5. 返回值
应返回dp[n]的值。

C++ 算法代码

class Solution {
public:
    int tribonacci(int n) {
        vector<int> v(n+1);

        if(n>=0) v[0]=0;
        if(n>=1)  v[1]=1;
        if(n>=2)  v[2]=1;

        for(int i=3;i<=n;i++)
        {
            v[i]=v[i-1]+v[i-2]+v[i-3];
        }
        return v[n];
    }
};

2. 三步问题（简单）

1. 题目链接

面试题 08.01. 三步问题 - 力扣（LeetCode）

2. 解法（动态规划）

算法思路
1. 状态定义
依经验和题意定义状态：dp[i]表示到达i位置时的方法总数。
2. 状态转移方程
按i位置的前一步情况分类讨论：
若dp[i]表示小孩上到第i阶楼梯的方式数，它等于前一步所有可能方式之和：
- 前一步上一级，dp[i] += dp[i - 1]；
- 前一步上两级，dp[i] += dp[i - 2]；
- 前一步上三级，dp[i] += dp[i - 3]；
综上，dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。需注意结果可能很大，要取模。计算时每一步相加都取模，避免溢出。
3. 初始化
由递推公式知，i=0、i=1、i=2时无法推导，因dp[-3]等无意义。题意给出dp[1] = 1，dp[2] = 2，dp[3] = 4，需提前初始化。
4. 填表顺序
毫无疑问是“从左到右”。
5. 返回值
应返回dp[n]的值。

代码实现

class Solution {
public:
const int MOD = 1e9 + 7;
int waysToStep(int n) {
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回
// 处理边界情况
if(n == 1 || n == 2) return n;
if(n == 3) return 4;
vector<int> dp(n + 1);
dp[1] = 1, dp[2] = 2, dp[3] = 4;
for(int i = 4; i <= n; i++)
dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
return dp[n];
}
}

3. 使用最小花费爬楼梯（简单）

1. 题目链接

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

2. 解法（动态规划）

算法思路一
1. 状态定义
按经验和题意定义：第一种，以i位置结尾，dp[i]表示到达i位置时的最小花费（注意：到达i位置时，i位置的花费不计入）。
2. 状态转移方程
根据前一步情况分类：
- 先到i-1位置，支付cost[i-1]，再走一步到i位置：dp[i - 1] + cost[i - 1]；
- 先到i-2位置，支付cost[i-2]，再走一步到i位置：dp[i - 2] + cost[i - 2]。
3. 初始化
由递推公式可知，需初始化i=0和i=1位置的值。易知dp[0] = dp[1] = 0，因无需花费即可站在0层和1层。
4. 填表顺序
根据“状态转移方程”，遍历顺序是“从左到右”。
5. 返回值
根据“状态定义和题意”，需返回dp[n]的值。

C++ 算法代码

class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size();

// 初始化一个 dp表
vector<int> dp(n + 1, 0);
// 初始化
dp[0] = dp[1] = 0;

// 填表
for (int i = 2; i < n + 1; i++)

// 根据状态转移方程得
dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);

// 返回结果
return dp[n]; }

};

解法二
1. 状态定义
第二种，以i位置为起点，dp[i]表示从i位置出发到达楼顶的最小花费。
2. 状态转移方程
根据前一步情况分类：
- 支付cost[i]，走一步到i+1位置出发：dp[i + 1] + cost[i]；
- 支付cost[i]，走两步到i+2位置出发：dp[i + 2] + cost[i]；
取最小花费，故dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]。
3. 初始化
为保证填表不越界，需初始化最后两个位置的值，依状态定义可知：dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2]
4. 填表顺序
根据“状态转移方程”，遍历顺序是“从右到左”。
5. 返回值
根据“状态定义和题意”，需返回dp[n]的值。

C++ 算法代码

class Solution
{
public:
int minCostClimbingStairs(vector<int>& cost)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表顺序
// 4. 返回值
int n = cost.size();
vector<int> dp(n);
dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
for(int i = n - 3; i >= 0; i--)
dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];
return min(dp[0], dp[1]);
}
}

4. 解码方法（中等）

1. 题目链接

91. 解码方法 - 力扣（LeetCode）

2. 解法（动态规划）

算法思路
1. 状态定义
依据以往经验，对于大多线性dp，常以“某个位置结束”来定义状态，这里尝试“以i位置结尾”结合题意定义：
dp[i]表示字符串中[0，i]区间内的编码方法总数。
2. 状态转移方程
定义好状态后，分析i位置的dp值由前面或后面信息推导。i位置的编码情况分两种：
- 让i位置的数单独解码成一个字母；
- 让i位置的数与i-1位置的数结合解码成一个字母。
分情况讨论：
- 让i位置的数单独解码：
- 解码成功：当i位置的数在[1, 9]间时，[0, i]区间的解码方法等于[0, i-1]区间的解码方法，此时dp[i] = dp[i - 1]；
- 解码失败：当i位置的数是0时，[0, i]区间无解码方法，dp[i] = 0。
- 让i位置的数与i-1位置的数结合解码：
- 解码成功：当结合的数在[10, 26]间时，[0, i]区间的解码方法等于[0, i-2]区间的解码方法，此时dp[i] = dp[i - 2]；
- 解码失败：当结合的数不在[10, 26]间时，[0, i]区间无解码方法，dp[i] = 0。
综上，dp[i]最终是上述解码成功情况的累加，状态转移方程（dp[i]初始化为0）：
- 当s[i]在[1, 9]间时：dp[i] += dp[i - 1]；
- 当s[i-1]与s[i]结合的数在[10, 26]间时：dp[i] += dp[i - 2]；
若两种情况都不满足，dp[i]为0。
3. 初始化
方法一（直接初始化）：
因可能用到i-1和i-2位置的dp值，需初始化前两个位置。
- 初始化dp[0]：
- 若s[0] == '0'，无编码方法，dp[0] = 0；
- 若s[0] != '0'，能编码成功，dp[0] = 1
- 初始化dp[1]：
- 若s[1]在[1，9]间，能单独编码，此时dp[1] += dp[0]（dp[1]初始为0）
- 若s[0]与s[1]结合的数在[10, 26]间，说明前两个字符有另一种编码方式，此时dp[1] += 1；
方法二（添加辅助位置初始化）：
可在最前加辅助结点，注意两点：
- 辅助结点值要保证后续填表正确；
- 下标映射关系
4. 填表顺序
毫无疑问是“从左到右”
5. 返回值
应返回dp[n - 1]的值，表示[0, n - 1]区间的编码方法数。

C++ 算法代码

class Solution
{
public:
int numDecodings(string s)
{
int n = s.size();
vector<int> dp(n); // 创建一个 dp表
// 初始化前两个位置
dp[0] = s[0] != '0';
if(n == 1) return dp[0]; // 处理边界情况
if(s[1] <= '9' && s[1] >= '1') dp[1] += dp[0];
int t = (s[0] - '0') * 10 + s[1] - '0';
if(t >= 10 && t <= 26) dp[1] += 1;
// 填表
for(int i = 2; i < n; i++)
{
// 如果单独编码
if(s[i] <= '9' && s[i] >= '1') dp[i] += dp[i - 1];
// 如果和前面的一个数联合起来编码
int t = (s[i - 1] - '0') * 10 + s[i] - '0';
if(t >= 10 && t <= 26) dp[i] += dp[i - 2];
}
// 返回结果
return dp[n - 1];
}
}

5. 不同路径（中等）

1. 题目链接

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

2. 解法（动态规划）

算法思路
1. 状态定义
对于“路径类”问题，状态表示有两种形式，这里选择第二种：dp[i][j]表示走到[i, j]位置处的方法总数。
2. 状态转移方程
分析可知，到达[i, j]位置前一步有两种情况：
- 从[i, j]位置的上方（[i-1, j]位置）向下走一步到[i, j]；
- 从[i, j]位置的左方（[i, j-1]位置）向右走一步到[i, j]。
因求方法数，状态转移方程为：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
3. 初始化
可加辅助结点，注意两点：
- 辅助结点值保证后续填表正确；
- 下标映射关系。
本题中，添加一行一列后，只需将dp[0][1]初始化为1。
4. 填表顺序
根据“状态转移方程”，填表顺序是“从上往下”填每一行，每行“从左往右”。
5. 返回值
根据“状态定义”，要返回dp[m][n]的值。

C++ 算法代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));

        dp[0][1]=1;

        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }

        return dp[m][n];
    }
};