典型问题—斐波那契类型

# 70. 爬楼梯 (opens new window)

状态定义：第 i 级台阶有dp[i]中方法；

转移方程：dp[i+1]=dp[i]+dp[i-1]；

初始状态：dp[0]=1,dp[1]=1；

返回值：dp[n]；

记忆化搜索：

class Solution {
    int[] memo;
    public int climbStairs(int n) {
        memo = new int[n+1];
        return dfs(n);
    }
    int dfs(int n){
        if(n<=2)
            return n;
        if(memo[n]>0)
            return memo[n];
        memo[n] = dfs(n-1)+dfs(n-2);
        return memo[n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

动态规划：

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

1
2
3
4
5
6
7
8
9
10
11

# 746. 使用最小花费爬楼梯 (opens new window)

状态定义：第 i 级台阶总花费；

状态转移：dp[i]=min(dp[i-1],dp[i-2])+cost[i]；

初始状态：dp[0]=cost[0]；dp[1]=min(cost[0]+cost[1],cost[1])=cost[1]；

返回值：dp[n]=min(dp[n-1],dp[n-2])，到 n级台阶无花费；

记忆化搜索：

class Solution {
    int[] memo;
    int[] cost;
    public int minCostClimbingStairs(int[] cost) {
        this.cost = cost;
        int n = cost.length;
        memo = new int[n+1];
        return dfs(n);
    }
    int dfs(int i){
        if(i==0||i==1)
            return cost[i];
        if(memo[i]!=0)
            return memo[i];
        memo[i] = Math.min(dfs(i-1),dfs(i-2))+(i==cost.length?0:cost[i]);
        return memo[i];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

动态规划：

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

1
2
3
4
5
6
7
8
9
10
11
12

# 198. 打家劫舍 (opens new window)

状态定义：偷第 i 间房屋偷窃到的最高金额；

状态转移：dp[i] =max(dp[i-2]+nums[i],dp[i-1])；

初始状态：dp[0]=nums[0]，dp[1]=max(nums[0],nums[1])；

返回值：dp[n-1]；

记忆化搜索：

从后向前思路：n不选，为f(n-1);n选，则为f(n-2)；

class Solution {
    int[] memo;
    int[] nums;
    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memo = new int[n];
        Arrays.fill(memo,-1);
        return dfs(n-1);
    }
    int dfs(int i){
        if(i<0) 
            return 0;
        if(memo[i]!=-1) 
            return memo[i];
        memo[i] = Math.max(dfs(i-1),dfs(i-2)+nums[i]);
        return memo[i];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

从前向后思路：返回[i,...)抢到的最大值；

class Solution {
    int[] memo;
    int[] nums;
    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memo = new int[n];
        Arrays.fill(memo,-1);
        return dfs(0);
    }
    int dfs(int i){
        if(i>=nums.length) 
            return 0;
        if(memo[i]!=-1) 
            return memo[i];
        memo[i] = Math.max(dfs(i+1),dfs(i+2)+nums[i]);
        return memo[i];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

动态规划：

class Solution {
    public int rob(int[] nums){
        int n = nums.length;
        if(n==1){
            return nums[0];
        }
        if(n==2){
            return Math.max(nums[0],nums[1]);
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

如何规避转移方程下标为负的情况？

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+2];
        for(int i=0;i<n;i++){
            dp[i+2] = Math.max(dp[i+1],dp[i]+nums[i]);
        }
        return dp[n+1];
    }
}

1
2
3
4
5
6
7
8
9
10

← 遍历dfs 典型dp—背包问题→