动态规划＜一＞初识动态规划

目录

认识动态规划

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];}