【动态规划】- 线性dp

目录

第 N 个泰波那契数

三步问题

使用最小花费爬楼梯

解码方法

数字三角形

 摘花生

---

第 N 个泰波那契数

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

1. 状态表示
   1. 是什么？dp表里面的值所表示的含义
   2. 怎么来？①题目要求->dp[ i ]表示第 i 个泰波那契数的值 ②经验+题目要求（多做题）③分析问题的过程中，发现重复子问题
2. 状态转移方程
   1. dp[ i ]等于什么->dp[ i ]=dp[ i-1 ]+dp[ i-2 ]+dp[ i-3 ]
3. 初始化
   1. 保证填表的时候不越界->dp[0]=0,dp[1]=dp[2]=1
4. 填表顺序
   1. 为了填写当前状态的时候，所需要的状态已经计算过了
5. 返回值
   1. 题目要求+状态表示

class Solution {public int tribonacci(int n) {// 处理边界情况：if (n == 0)return 0;if (n == 1 || n == 2)return 1;// 1. 创建dp表int[] dp = new int[n + 1];// 2. 初始化dp[0] = 0;dp[1] = dp[2] = 1;// 3. 填表for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}// 4. 返回值return dp[n];}
}

空间优化： 

class Solution {// 空间优化：public int tribonacci(int n) {// 处理边界情况：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;}// 4. 返回值return d;}
}

三步问题

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

1. 状态表示
   1. 经验+题目要求
   2. 以 i 位置为结尾，根据题目要求做替换
   3. dp[ i ]表示到达 i 位置时，共有多少方法
2. 状态转移方程
   1. 以 i 位置的状态，最近的一步来划分问题 ①dp[ i-1 ]->dp[ i ] ②dp[ i-2 ]->dp[ i ] ③dp[ i-3 ]->dp[ i ]
   2. dp[ i ]=dp[ i-1 ]+dp[ i-2 ]+dp[ i-3 ]
3. 初始化->dp[1]=1,dp[2]=2,dp[3]=4
4. 填表顺序->从左往右
5. 返回值->dp[ n ]

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

使用最小花费爬楼梯

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

解法一：

1. 状态表示
   1. 经验+题目要求
   2. 以 i 位置为结尾，根据题目要求做替换->dp[ i ]表示到达 i 位置时最小花费
2. 状态转移方程
   1. 用之前或之后的状态推导出dp[ i ]的值
   2. 根据最近的一步来划分问题①dp[ i-1 ]->dp[ i ]②dp[ i-2 ]->dp[ i ]
   3. dp[ i ]=min(dp[ i-1 ]+cost[ i-1 ],dp[ i-2 ]+cost[ i-2 ])
3. 初始化->保证填表的时候不越界dp[0]=dp[1]=0
4. 填表顺序->从左往右
5. 返回值->dp[n]

class Solution {public int minCostClimbingStairs(int[] cost) {// 1. 创建dp表int n = cost.length;int[] dp = new int[n + 1];// 2. 初始化// 3. 填表for (int i = 2; i <= n; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}// 4. 返回值return dp[n];}
}

解法二： 

1. 状态表示
   1. 经验+题目要求
   2. 以 i 位置为起点，根据题目要求做替换
2. 状态转移方程
   1. 支付cost[ i ]，往后走一步，从 i+1 的位置出发到终点->dp[ i+1 ]+cost[ i ]
   2. 支付cost[ i ]，往后走两步，从 i+2 的位置出发到终点->dp[ i+2 ]+cost[ i ]
   3. dp[ i ]=min(dp[ i+1 ]+cost[ i ],dp[ i+2 ]+cost[ i ])
3. 初始化->dp[ n-1 ]=cost[ n-1 ],dp[ n-2 ]=cost[ n-2 ]
4. 填表顺序->从右往左
5. 返回值->min(dp[0],dp[1])

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

解码方法

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

1. 状态表示
   1. 经验+题目要求
   2. 以 i 位置为结尾，根据题目要求做替换
   3. dp[ i ]表示以 i 位置为结尾时，解码方法的总数
2. 状态转移方程
   1. 根据最近的一步划分问题
   2. ①s[ i ]单独解码（1~9之间成功->dp[ i-1 ]，否则为0） ②s[ i-1 ]与s[ i ]解码（10~26之间成功->dp[ i-2 ]，否则为0）
   3. dp[ i ]=dp[ i-1 ]+dp[ i-2 ]（解码成功时）
3. 初始化
   1. dp[0]=1（1~9）或0,dp[1]=0或1（10~26）或2（1~9，1~9）
4. 填表顺序->从左往右
5. 返回值->dp[ n-1 ]

class Solution {public int numDecodings(String ss) {// 1. 创建dp表int n = ss.length();char[] s = ss.toCharArray();int[] dp = new int[n];// 2. 初始化if (s[0] != '0')dp[0] = 1;// 处理边界情况if (n == 1)return dp[0];// 初始化第二个位置if (s[1] != '0' && s[0] != '0')dp[1] += 1;int t = (s[0] - '0') * 10 + s[1] - '0';if (t >= 10 && t <= 26)dp[1] += 1;// 3. 填表for (int i = 2; i < n; i++) {// 先处理第一种情况if (s[i] != '0')dp[i] += dp[i - 1];// 处理第二种情况int tt = (s[i - 1] - '0') * 10 + s[i] - '0';if (tt >= 10 && tt <= 26)dp[i] += dp[i - 2];}// 4. 返回值return dp[n - 1];}
}

空间优化：

class Solution {public int numDecodings(String ss) {// 1. 创建dp表int n = ss.length();char[] s = ss.toCharArray();int[] dp = new int[n + 1];// 2. 初始化dp[0] = 1;// 保证后续填表是正确的if (s[1 - 1] != '0')dp[1] = 1;// 3. 填表for (int i = 2; i <= n; i++) {// 先处理第一种情况if (s[i - 1] != '0')dp[i] += dp[i - 1];// 处理第二种情况int tt = (s[i - 2] - '0') * 10 + s[i - 1] - '0';if (tt >= 10 && tt <= 26)dp[i] += dp[i - 2];}// 4. 返回值return dp[n];}
}

数字三角形

3304. 数字三角形 - AcWing题库

import java.util.*;
public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[][] dp=new int[n+1][n+1];for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i][j]=sc.nextInt();dp[i][j]+=Math.max(dp[i-1][j],dp[i-1][j-1]);}}int ret= n%2==1?dp[n][n/2+1]:Math.max(dp[n][n/2],dp[n][n/2+1]);System.out.print(ret);}
}

 摘花生

1015. 摘花生 - AcWing题库

import java.util.*;
public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int t=sc.nextInt();for(int i=0;i<t;i++){// t组数据：int r=sc.nextInt();int c=sc.nextInt();int[][] dp=new int[r+1][c+1];int[][] hs=new int[r+1][c+1];// 花生数量for(int x=1;x<=r;x++){for(int y=1;y<=c;y++){hs[x][y]=sc.nextInt();}}for(int x=1;x<=r;x++){for(int y=1;y<=c;y++){dp[x][y]=hs[x][y]+Math.max(dp[x-1][y],dp[x][y-1]);}}System.out.println(dp[r][c]);}}
}