动态规划——斐波那契模型

简介: 本文介绍了动态规划的基本步骤及其在几个典型问题中的应用。首先概述了动态规划的四个关键步骤:状态表示、状态转移方程、初始化及填表顺序,并说明了如何确定返回值。接着通过具体实例讲解了第 N 个泰波那契数、三步问题、使用最小花费爬楼梯以及解码方法等问题的求解过程,详细阐述了每一步的具体实现方法与代码示例。最后还讨论了如何优化初始化过程以简化编码。

动态规划的步骤:

  1. 状态表示。所谓状态表示就是 dp 表里的值表示什么含义,那么状态表示怎么找呢?
  1. 题目要求
  2. 经验(以某一个位置为结尾 / 起点) + 题目要求
  3. 分析问题的过程中发现重复子问题
  1. 状态转移方程。dp[ i ] 等于什么
  2. 初始化。保证填表的时候不越界
  3. 填表顺序。保证填写当前状态时,所需要的状态已经计算过了,初始化之后,下标的映射关系要一致
  4. 返回值。根据题目要求和状态表示进行返回


1. 第 N 个泰波那契数

1137. 第 N 个泰波那契数

这题比较简单,直接秒了

状态表示:dp[i] 表示第 i 个泰波那契数的值

状态转移方程: dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

初始化:把前三个数初始化

填表顺序:从左到右

返回值:返回 dp[n]

class Solution {
    public int tribonacci(int n) {
        int[] dp = new int[38];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        if(n < 3){
            return dp[n];
        }
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }
}

还可以对上述代码进行空间优化,因为在求第 i 个位置的时候,只需要知道前三个数即可,每次求一个位置都是这样,所以就可以定义三个变量,不断地更新,实现滚动数组的效果

滚动数组空间优化版本:

class Solution {
    public int tribonacci(int n) {
        int sum = 0;
        int a = 0,b = 1,c = 1;
        if (n == 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        for (int i = 3; i <= n; i++) {
            sum = a + b + c;
            a = b;
            b = c;
            c = sum;
        }
        return sum;
    }
}

2. 面试题 08.01. 三步问题

面试题 08.01. 三步问题

状态表示:dp[i] 表示到达第 i 个位置时的方案数

状态转移方程: dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

初始化:计算前三个数的方案数,把前三个数初始化

填表顺序:从左到右

返回值:返回 dp[n]

class Solution {
    public int waysToStep(int n) {
        long a = 1,b = 2,c = 4;
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;
        long res = 0;
        for(int i = 4;i <= n;i++){
            res = (a + b + c) % 1000000007;
            a = b;
            b = c;
            c = res;
        }
        return (int) res;
    }
}

3. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

状态表示:dp[i] 表示到达第 i 个位置时的最小花费

状态转移方程:

dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

初始化:由于需要用到前两个数,所以需要把 dp[0] 和 dp[1] 初始化,因为刚开始可以直接从 0 下标或 1 下标出发,所以可以初始化为 0

填表顺序:从左到右

返回值:返回 dp[n],楼梯顶部为 n 下标,也就是

Math.min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2])

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        if (n == 1 ) return 0;
        if(n == 2) return Math.min(cost[0],cost[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 Math.min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2]);
    }
}

还有第二种状态表示可以解决:

dp[i] 表示从 i 位置出发,到达楼顶的最小花费

初始化:用这种方法的话,就需要用到后面两个元素,所以刚开始初始化需要把最后的两个元素初始化

初始 dp[n - 1] 时就表示从 n - 1 位置支付 cost[n - 1] 就可以直接到达楼顶,dp[n - 2] 时支付 cost[n - 2] 也可以直接到达楼顶

填表顺序:从后往前

最后的返回值也就是 dp[0] 和 dp[1] 的最小值

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        if (n == 1 ) return 0;
        if(n == 2) return Math.min(cost[0],cost[1]);
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];
        for(int i = n - 3;i >= 0;i--){
            dp[i] = Math.min(dp[i + 1] + cost[i],dp[i + 2] + cost[i]);
        }
        return Math.min(dp[0],dp[1]);
    }
}

4. 解码方法

91. 解码方法

只有在 1 ~ 26 范围内的数字才可以解码,有前导 0 或者超过 26 的都不能解码

状态表示:以 i 位置为结尾时,解码方法的总数

此时就会有两种状态,s[i] 位置单独解码,s[i] 和 s[i - 1] 结合解码,每一种状态又可以分为解码成功和解码失败两种情况

状态转移方程:(根据最近的一步划分问题)根据情况来判断 dp[i] 是否加上 dp[i - 1] 和 dp[i - 2]

初始化:初始化 dp[0] 的时候也是有两种情况的,解码成功就是 1,解码失败就是 0,初始化 dp[1] 的时候就有三种情况了,由于是两个数字,所以就需要考虑两个单独解码和结合起来解码,如果都解码失败就是 0,如果单独解码成功就加 1,如果结合起来解码又成功了就再加上 1

填表顺序:从左往右

返回值:返回 dp[n - 1]

class Solution {
    public int numDecodings(String s) {
        int[] dp = new int[s.length()];
        char[] chars = s.toCharArray();
        if(chars[0]!='0'){
            dp[0] = 1;
        }
        if(s.length() == 1) return dp[0];
        if(chars[0]!='0'&&chars[1]!='0') dp[1] += 1;
        int t = (chars[0] - '0') * 10 + chars[1] - '0';
        if(t >= 10 && t <= 26) dp[1]+=1;
        for(int i = 2;i < s.length();i++){
            int tmp = (chars[i - 1] - '0') * 10 + chars[i] - '0';
            if(chars[i] != '0') dp[i] += dp[i - 1];
            if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
        }
        return dp[s.length() - 1];
    }
}

上面的代码的初始化过程看起来很麻烦,还可以优化一下:

上面初始化时是 dp[1] 比较麻烦的,可以把 dp 数组多开一个元素,

class Solution {
    public int numDecodings(String s) {
        int[] dp = new int[s.length() + 1];
        char[] chars = s.toCharArray();
        dp[0] = 1;
        if(chars[0]!='0'){
            dp[1] = 1;
        }
        if(s.length() == 1) return dp[1];
        for(int i = 2;i <= s.length();i++){
            int tmp = (chars[i - 2] - '0') * 10 + chars[i - 1] - '0';
            if(chars[i - 1] != '0') dp[i] += dp[i - 1];
            if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
        }
        return dp[s.length()];
    }
}


这一题和珠宝最大和是非常相似的,不过就是这里要求最小的路径和

状态表示:dp[i][j] 表示到达 (i , j) 时的最小路径和

状态转移方程:

初始化:

返回值:dp[m][n]

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length,n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 0;i < m + 1;i++){
            for(int j = 0;j < n + 1;j++){
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[1][0] = dp[0][1] = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                dp[i+1][j + 1] = Math.min(dp[i + 1][j],dp[i][j+1]) + grid[i][j];
            }
        }
        return dp[m][n];
    }
}
相关文章
|
5月前
|
算法 C++
【动态规划】斐波那契数列模型(C++)
【动态规划】斐波那契数列模型(C++)
动态规划| 【斐波那契数列模型 】|1137.第N个泰波那锲数
动态规划| 【斐波那契数列模型 】|1137.第N个泰波那锲数
|
6月前
|
算法
算法修炼-动态规划之斐波那契数列模型
算法修炼-动态规划之斐波那契数列模型
|
机器学习/深度学习 存储 算法
回溯法求解N皇后问题
回溯法求解N皇后问题
143 0
|
算法 C++
记忆化搜索算法的实现
记忆化搜索算法的实现
记忆化搜索算法的实现
|
算法 JavaScript 前端开发
☮斐波那契数列与动态规划
☮斐波那契数列与动态规划
116 0
☮斐波那契数列与动态规划
|
机器学习/深度学习 算法
斐波拉契数列的递推递归求解算法
斐波拉契数列的递推递归求解算法
107 0
|
Java 机器人
最小路径和——动态规划求解(Java实现)
最小路径和——动态规划求解(Java实现)
144 0
|
Java
青蛙跳台阶问题——动态规划求解(Java实现)
青蛙跳台阶问题——动态规划求解(Java实现)
266 0