动态规划（1）斐波那契数列模型
动态规划算法流程：
1、状态表示：
指的是dp（dynamic programming）表里面的值所表示的含义
如何得出：1、题目要求
2、经验+题目要求
3、分析问题的过程中发现重复子问题
2、状态转移方程
dp[i]等于什么
3、初始化
保证填表的时候不越界
4、填表顺序
为了填写当前状态的时候，所需要的状态已经计算过了
5、返回值
结合题目要求+状态表示
例题
1、1137. 第 N 个泰波那契数 - 力扣（LeetCode）
1、状态表示
根据题目要求，dp[i]表示第i个泰波那契数的值
2、状态转移方程
dp[i]依赖于前三个数dp[i-1]、dp[i-2]、dp[i-3]
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
3、初始化
为了使dp[i-1]、dp[i-2]、dp[i-3]不越界，需要初始化dp[0]=0、dp[1]=1、dp[2]=1
4、填表顺序
从左向右
5、返回值
dp[n]
代码实现：
class Solution {
public int tribonacci(int n) {
//边界情况
if(n==0) return 0;
if(n==1||n==2) return 1;
//状态方程
int[] dp = new int[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];
}
}空间优化：滚动数组
O(n)-->O(1)
滚动操作：a = b, b = c, c = d
注意不能先将c = d,不然b就找不到c之前的位置了,要从前向后赋值
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;
}
return d;
}
}2、面试题 08.01. 三步问题 - 力扣（LeetCode）
题目解析
楼梯有1阶时，直接从起始位置迈一步就到1阶，共1种；有2阶时，可以从起始位置买两步，或者从1阶迈一步，共两种；有三阶时，可以从起始位置迈三步，从1阶迈两步，从二阶迈一步，总共四种。初学者可能会有疑问为什么是四种，因为迈到二阶的方法就两种，从二阶迈一步到三阶的结果还是两种而不是三种，因为这里指的是方法数，不是迈的步数，直接再迈二阶的方法后面加上->3，如下图。所以总方法是前三个迈台阶方法数之和。
1、状态表示
根据题目加经验：以i位置为结尾，dp[i]表示正好到达第i个台阶总共有dp[i]种方法
2、状态转移方程
3、初始化
因为dp[0]无意义就略去
dp[1]=1;dp[2]=2;dp[3]=4
4、填表顺序
从左往右
5、返回值
dp[n]
细节处理，因为题目要对结果取模，所以要对每一次求和都要取模
dp[i] = ((dp[i-1]+dp[i-2])%(1e9+7)+dp[i-3])%(1e9+7)
代码实现：
class Solution {
public int waysToStep(int n) {
int Mod = (int)1e9+7;
if(n==1 || n==2) return n;
if(n==3) return 4;
//建表
int[] dp = new int[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、LCR 088. 使用最小花费爬楼梯 - 力扣（LeetCode）
题目解析:
先确定楼顶，如果楼顶为下标[n-1]的位置，则示例1的最小花费为10元，而实际为15，因此楼顶为n的位置。要到达某一位置台阶的花费最小，如果迈两步则总花费为到达i-2的最小花费+cost[i-2]，如果迈一步则总花费为到达i-1的最小花费+cost[i-1]，因此到此位置的最小花费为迈一步的最小花费与买两步的最小花费的最小值。
示例2：
1、状态表示
根据题目加经验：以i位置为结尾，dp[i]表示正好到达第i个台阶最小的花费为dp[i]
2、状态转移方程
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) {
int n = cost.length;
//建表
int[] dp = new int[n+1];
//初始化
dp[0] = 0;
dp[1] = 0;
//填表
for(int i=2;i<=n;i++)
dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
//返回值
return dp[n];
}
}4、91. 解码方法 - 力扣（LeetCode）
题目解析:
解码方式总共有两种，单独解码和两数一起解码
但也有不能解码的情况如下。
算法原理：
1、状态表示
dp[i]表示以i位置为结尾，解码方法的总数
2、状态转移方程
根据最近的一步，划分问题，dp[i]=dp[i-1]+dp[i-2]
‘单独解码’成功情况的解释，‘一起解码’同理
3、初始化
dp[0]和dp[1]
4、填表顺序
从左往右
5、返回值
dp[n-1]
代码实现：
class Solution {
public int numDecodings(String s) {
//1、创建dp表
int n = s.length();
int[] dp = new int[n];
//2、初始化
if(s.charAt(0)!='0') dp[0] = 1;
if(n==1) return dp[0]; //边界情况
char a = s.charAt(0);
char b = s.charAt(1);
if(b!='0'&&a!='0') dp[1]+=1;
int t = (a-'0')*10+(b-'0');
if(t>=10&&t<=26) dp[1]+=1;
//3、填表
for(int i = 2;i<n;i++)
{
if(s.charAt(i)>'0'&&s.charAt(i)<='9')
dp[i] += dp[i-1];
t = (s.charAt(i-1)-'0')*10+(s.charAt(i)-'0');
if(t>=10&&t<=26)
dp[i] += dp[i-2];
}
//4、返回值
return dp[n-1];
}
}我们发现初始化的代码很复杂并且逻辑和填表的代码类似，因此我们可以添加辅助节点的方法来简化代码。
处理边界问题以及初始化的技巧：
虚拟位置初始化：为了以后填表正确，dp[0]需要为1，因为如果dp[2]和dp[1]填表正确，那么前面的填表也是正确的，如果为0说明前面解码不成功，因此要为1.
下标映射关系：根据上图，初始化只处理了s[0], s[1]并未处理，因此填表处理时的s下标为i-1
class Solution {
public int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
if(s.charAt(0)!='0') dp[1] = 1;
else return 0;
for(int i = 2;i<=n;i++)
{
if(s.charAt(i-1)>'0'&&s.charAt(i-1)<='9')
dp[i] += dp[i-1];
if((s.charAt(i-2)-'0')*10+(s.charAt(i-1)-'0')>=10&&(s.charAt(i-2)-'0')*10+(s.charAt(i-1)-'0')<=26)
dp[i] += dp[i-2];
}
return dp[n];
}
}原文地址：https://blog.csdn.net/2301_79783967/article/details/142744621
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！