动态规划基础理论

文章：1. 动态规划理论基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，这一点区别于贪心，贪心没有状态推导，而是从局部直接选最优的。

动态规划中dp[i]是由dp[j - weight[i]]推导出来的，然后取max(dp[j],dp[j - weight[i]]+value[i])。

所以贪心解决不了动态规划的问题。

动态规划的解题步骤

动态规划五部曲：

1.确定dp数组（dp take）以及下标的含义

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

5.举例推导dp数组

509.斐波那契数

文章：2. 斐波那契数

题目：509. 斐波那契数

【思路】

动态规划五部曲：

1.确定dp数组以及下标的含义

dp[i]的含义为：第i个数的斐波那契数值是dp[i]

2.确定递归公式

状态转移方程：dp[i] = dp[i-1] + dp[i-2]

3.dp数组初始化

dp[0] = 0;

dp[1] = 1;

4.确定遍历顺序

从递归公式可以看出，dp[i]是依赖dp[i-1] + dp[i-2]的，那么遍历的顺序一定是从前到后遍历的。

5.举例推导顺序

…

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int fib(int n) {
        //1.确定dp数组的下标i含义为：第i个斐波那契数是dp[i]
        //2.确定状态转移方程
        if(n <= 1){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i <= n ; i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
  • Go实现

发现居然可以只使用变量就完成斐波那契，真的牛

1
2
3
4
5
6
7
8
9
10
11
12
func fib(n int) int {
    if n <= 1 {
        return n
    }
    a,b,c := 0,1,0
    for i:=1 ; i<n ; i++ {
        c = a+b
        a = b
        b = c
    }
    return c
}

70.爬楼梯

文章：3. 爬楼梯

题目：70. 爬楼梯

视频：带你学透动态规划-爬楼梯（对应力扣70.爬楼梯）| 动态规划经典入门题目_哔哩哔哩_bilibili

【思路】

1.确认dp数组及其下标含义

dp[i] : 爬到第i层楼梯，有dp[i]层方法。

2.确定递推公式

dp[i] = dp[i-1]+dp[i-2]

3.dp数组初始化

dp[1] = 1

dp[2] = 2

4.确定遍历顺序

从前向后遍历

5.举例推导

…

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int climbStairs(int n) {
    if(n <=1)return n;
    int[] dp = new int[n+1];
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3;i<=n;i++){
        dp[i] = dp[i-2]+dp[i-1];
    }
    return dp[n];

 }
};
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
func climbStairs(n int) int {
    if n <= 1{
        return n 
    }
    dp := make([]int,n+1)
    dp[1] = 1
    dp[2] = 2
    for i := 3;i <= n ; i++{
        dp[i] = dp[i-1]+dp[i-2]
    } 
    return dp[n]
}

746.使用最小花费爬楼梯

文章：4. 使用最小花费爬楼梯

题目：746. 使用最小花费爬楼梯

【思路】

1.确定dp数组以及下标的含义

dp[i]：到达第i台阶所花费的最少体力为dp[i]

2.确定递归公式

对于dp[i]

dp[i-1] 到dp[i] :dp[i-1]+cost[i-1]

dp[i-2] 到dp[i] : dp[i-2]+cost[i-2]

需要选出最小的dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3.dp数组如何初始化

dp[i]由dp[i-1]或dp[i-2]推出，只需要初始化dp[0]和dp[1]，其他都在该基础上推出就好1

4.确定遍历顺序

从前往后

5.举例推导dp数组

…

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //获得dp[i]的途径是：dp[i-1],dp[i-2]
        //1.确定dp数组及其下标
        int[] dp = new int[cost.length+1];
        //2.确认递推公式 dp[i] = Math.max(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
        //3.数组初始化
        dp[0] = 0;
        dp[1] = 0;
        //4.确认遍历顺序
        for(int i = 2 ; i <= cost.length;i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        //5.推导
        return dp[cost.length];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func minCostClimbingStairs(cost []int) int {
    dp := make([]int,len(cost)+1)
    dp[0],dp[1] = 0,0
    for i:=2;i<=len(cost);i++{
        dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
    }
    return dp[len(cost)]
}   
func min(a,b int)(res int){
    if a >b{
        return b
    } 
    return a
}

【算法总结】

  • 斐波那契数列、爬楼梯、使用最小花费爬楼梯：使用了动态规划五部曲进行分析。