动态规划＜一＞初识动态规划
目录
认识动态规划
LeetCodeOJ练习
斐波那契数列模型
认识动态规划
1.动态规划是一种用于解决优化问题的算法策略。
2.它的核心原理是把一个复杂的问题分解为一系列相互关联的子问题。通过先求解子问题，并且记录这些子问题的解（通常用一个表格之类的存储结构），避免重复计算，然后基于这些子问题的解来构建原问题的解
3.解题步骤
这里通过一道题进行说明一些概念
传送门:LeetCode<1137> 第 N 个泰波那契数
1.创建一个dp表(一般用数组)
2.确定状态表示
状态表示的话，简单理解就是dp表里面的值所代表的含义
对于此题的话，就是dp[i]表示的含义为第i个泰波那契数
该如何确定状态表示:
(1)可以根据题目要求，对于本题就是
(2)经验和题目要求
(3)分析问题的过程中，发现重复子问题
3.确定状态转移方程
简单说就是求出dp[i]等于什么 对于本题就是dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
4.初始化
确定初始状态的值，保证填表时不发生越界
对于此题就是dp[0],dp[1],dp[2]必须初始化，若通过状态转移方程计算的话，就会发生越界
5.填表顺序
确定是从左向右，还是从右向左的顺序填表，确保填写当前状态的时候，所需要的状态已经计算过了，对于本题就是从左向右的顺序
6.返回结果
根据题目要求和具体的状态表示，对于此题就是返回dp[n]
7.空间优化(不是必须)
因为创建dp表，导致空间复杂度为O(N),在这里我们可以用滚动数组进行优化
通过几个变量来降低空间复杂度
当我们依次往后求dp[i]时，前面的一些状态可以舍去，仅仅用中间若干个有效的状态，比如求dp[5]只需要知道dp[4],dp[3],dp[2]就可以了，像这样的情况就可以使用滚动数组来优化
本题具体代码
没有做优化的版本
int tribonacci(int n) {//1.创建dp表//2.初始化//3.填表//4.返回值//处理边界情况if(n==0) return 0;if(n==1 || n==2) return 1;vector<int> dp(n+1);dp[0]=0,dp[1]=dp[2]=1;for(int i=3;i<=n;++i)dp[i]=dp[i-1]+dp[i-2]+dp[i-3];return dp[n];}优化的版本
int tribonacci(int n) {//1.创建dp表//2.初始化//3.填表//4.返回值//处理边界情况if(n==0) return 0;if(n==1 || n==2) return 1;int a=0,b=1,c=1,d=0;for(int i=3;i<=n;++i){d=a+b+c;a=b,b=c,c=d;//滚动操作}return d;}LeetCodeOJ练习
斐波那契数列模型
1.<面试题08.01> 三步问题
画图分析:
使用动态规划解决此题的步骤
1.创建dp表
2.确定状态表示
对于一般题都是集合经验和题目要求来确定
常见的经验有:以i位置为结尾xxx;以i位置为开始xxx 对于本题dp[i]表示到i位置的走法数
3.确定状态转移方程
确定方法一般为:以当前i位置状态最近的一步来划分问题，将划分的每个子问题用dp[x]表示
4.初始化，防止出现越界 对dp[1],dp[2],dp[3]进行初始化
5.填表顺序 从左往右
6.返回结果 dp[n]
具体代码:注意细节问题要将相加的结果模1e9+7，防止越界
int waysToStep(int n) {//1.创建dp表//2.初始化//3.填表//4.返回值const int MOD=1e9+7;//处理边界防止越界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];}2.LeetCode<746> 使用最小花费爬楼梯
画图分析:
使用动态规划解决此题的步骤:
1.创建dp表
2.确定状态表示
根据经验+题目要求，此处的dp[i]可以表示到达i位置时的最下花费
或者dp[i]表示从i位置开始到顶楼的最小花费
3.确定状态转移方程
(1)dp[i]可以表示到达i位置时的最下花费
对应代码
int minCostClimbingStairs(vector<int>& cost) {//1.创建dp表//2.初始化//3.填表//4.返回结果int n=cost.size();vector<int> dp(n+1);dp[0]=dp[1]=0;for(int i=2;i<=n;++i){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}(2) dp[i]表示从i位置开始到顶楼的最小花费
对应代码:
int minCostClimbingStairs(vector<int>& cost) {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]=cost[i]+min(dp[i+1],dp[i+2]);return min(dp[0],dp[1]);}3.LeetCode<91> 解码方法
使用动态规划解决此题的步骤
1.创建dp表
2.确定状态表示
方法依旧是根据经验+结合题意
dp[i]表示以i位置为结尾，解析方法的总数(从开始解析到i位置的方法总数)
3.确定状态转移方程
根据最近的一步，划分问题
具体代码为
int numDecodings(string s) {//1.创建dp表//2.初始化//3.填写dp表//4.返回结果int n = s.size();vector<int> dp(n); // 创建⼀个 dp表// 初始化前两个位置dp[0] = s[0] != '0';if(n == 1) return dp[0]; // 处理边界情况if(s[1]!='0') 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]!='0') 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];}对于上述代码我们会发现初始化操作和填写表操作几乎一致，在这里我们就可以对边界问题和初始化问题做优化的
优化的方法为添加虚拟头结点，使新dp表和旧dp表产生如下的映射关系
这里有两个需要注意的问题
(1)虚拟节点里面的值，要确保后面的填表也是正确的
(2)新旧dp表下标间的映射关系
对于(1)的话，新的dp表中，对于计算dp[2]=dp[1]+dp[0],dp[1]是直接映射下来的不用管，重点是dp[0]中的值，当球dp[2]要用到dp[0]时，若原字符串中的第一个和第二个位置字符拼起来能解码成功时，说明s[0]也是可以单独解码成功的，若dp[0]=0的话，就会缺失这个能单独解码的情况，所以dp[0]=1
优化后的代码
int numDecodings(string s) {//1.创建dp表//2.初始化//3.填写dp表//4.返回结果int n = s.size();vector<int> dp(n+1); // 创建⼀个 dp表// 初始化前两个位置dp[0] = 1;dp[1]=s[1-1]!='0';for(int i = 2; i <= n; i++){// 如果单独编码if(s[i-1]!='0') dp[i] += dp[i - 1];// 如果和前⾯的⼀个数联合起来编码int t = (s[i - 2] - '0') * 10 + s[i-1] - '0';if(t >= 10 && t <= 26) dp[i] += dp[i - 2];}// 返回结果return dp[n];}