动态规划-入门三道题

1137. 第 N 个泰波那契数

题目描述：
在这里插入图片描述
状态表示:
dp[i]表示第i个泰波那契数。
状态转移方程：
dp[i]=dp[i-3]+dp[i-2]+dp[i-1]。
初始化:
动态规划问题的初始化就是为了去避免初始情况下的越界问题。这里就对dp[0]=0,dp[1]=1,dp[2]=1这样进行初始化即可，题目已经给出了，非常简单。
填表顺序:
显而易见填表顺序为从左到右。
返回值:
因为dp[i]表示第i个泰波那契数，题目要求计算第n个斐波那契数，因此返回dp[n]即可。
代码如下:
经过以上过程之后编写代码还要注意一个细节，注意要提前根据n的大小进行判断，如果数组大小小于等于2但是未经过判断，后面的初始化就会出现越界问题。

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

题目链接
时间复杂度:O(n)
空间复杂度:O(n)
空间优化版本：

class Solution {public int tribonacci(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}if (n == 2) {return 1;}int num1 = 0;int num2 = 1;int num3 = 1;int num4 = 0;for (int i = 0; i <= n - 3; i++) {num4 = num1 + num2 + num3;num1 = num2;num2 = num3;num3 = num4;}return num3;}
}

面试题 08.01. 三步问题

题目描述:
在这里插入图片描述
状态表示：
dp[i]表示达到第i阶台阶有多少种方法。
状态转移方程：
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]。
初始化：
还是为了防止越界，初始化dp[1]=0,dp[2]=2,dp[0]=1。
填表顺序：
从左至右。
返回值：
返回dp[n]。
代码如下：

class Solution {public int waysToStep(int n) {int[] dp = new int[n + 1];if (n == 0 || n == 1) {return 1;}if (n == 2) {return 2;}dp[0] = 1;dp[1] = 1;dp[2] = 2;int MOD = (int) 1e9 + 7;for (int i = 3; i <= n; i++) {dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;}return dp[n];}
}

题目链接
时间复杂度:O(n)
空间复杂度:O(n)

746. 使用最小花费爬楼梯

题目描述:
在这里插入图片描述
状态表示:
第一种方法，dp[i]表示到达第i个台阶使用的最低费用。
第二种方法，dp[i]表示从第i个台阶到达最顶部的最低费用。
状态转移方程:
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。
dp[i]=min(dp[i+1]+dp[i+2])+cost[i]。
初始化：
方法一要避免越界，初始化dp[0]=0,dp[1]=0。
方法二要避免越界，初始化dp[n-1]=cost[i],dp[n]=0。
填表顺序:
方法一从左至右，方法二从右至左。
返回值:
方法一返回值为dp[n]，这里的n是cost数组的长度。
方法二返回值为min(dp[0],dp[1])。
方法一代码如下:

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

方法二代码如下：

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