动态规划

本质：空间换时间

求解步骤：

  1. 设计状态
  2. 确定状态转移方程
  3. 确定初始状态
  4. 执行状态转移
  5. 计算最终的解

题目

递推

力扣第70题-爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解答：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int climbStairs(int n) {
        int[] F=new int[46];
        F[0]=F[1]=1;
        for(int i=2;i<=n;i++){
            F[i]=F[i-1]+F[i-2];
        }
        return F[n];
    }
}

力扣第509题-斐波那契数列

解答：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int fib(int n) {
        int[] F=new int[32];
        F[0]=0;
        F[1]=1;
        for(int i=2;i<=n;i++){
            F[i]=F[i-1]+F[i-2];
        }
        return F[n];
    }
}

力扣第1137题-第 N 个泰波那契数

解答：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int tribonacci(int n) {
        int[] F=new int[38];
        F[0]=0;
        F[1]=1;
        F[2]=1;
        for(int i=3;i<=n;i++){
            F[i]=F[i-1]+F[i-2]+F[i-3];
        }
        return F[n];
    }
}

力扣第746题-使用最小花费爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n=cost.length;
        int[] F=new int[n+1];
        F[0]=0;
        F[1]=0;
        for(int i=2;i<=n;i++){
            F[i] = Math.min(F[i - 1] + cost[i - 1], F[i - 2] + cost[i - 2]);
        }
        return F[n];
    }
}

力扣第198题-打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==1) return nums[0];
        if(n==0) return 0;
        int[] F=new int[n+1];
        F[0]=nums[0];
        F[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
            F[i]=Math.max(F[i-2]+nums[i],F[i-1]);
        }
        return F[n-1];
    }
}

力扣第53题-最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int[] f=new int[n];
        f[0] = nums[0];
        int ans=f[0];
        for(int i=1;i<n;i++){
            f[i]=Math.max(f[i-1],0)+nums[i];
            ans=Math.max(ans,f[i]);
        }
        return ans;
    }
}

矩阵

力扣第62题-不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

力扣第64题-最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int[][] dp=new int[m+1][n+1];
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++){
            dp[i][0]=grid[i][0]+dp[i-1][0];
        }
        for(int j=1;j<n;j++){
            dp[0][j]=grid[0][j]+dp[0][j-1];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
            }
        }
        return dp[m-1][n-1];
    }
}

力扣第63题-不同路径 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][] dp=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <n; j++) {
                dp[i][j] = 0;
            }
        }

        for(int i=0;i<n;i++){
            dp[0][i]=1;
            if(obstacleGrid[0][i]==1){
                dp[0][i]=0;
                break;
            }
        }
        for(int i=0;i<m;i++){
            dp[i][0]=1;
            if(obstacleGrid[i][0]==1){
                dp[i][0]=0;
                break;
            }
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                }
            }
        }
        return dp[m-1][n-1];
    }
}

力扣第1594题-矩阵的最大面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int maxProductPath(int[][] grid) {
        final int MOD = 1000000000 + 7;
        int m = grid.length, n = grid[0].length;
        long[][] maxgt = new long[m][n];
        long[][] minlt = new long[m][n];

        maxgt[0][0] = minlt[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] * grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            maxgt[i][0] = minlt[i][0] = maxgt[i - 1][0] * grid[i][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (grid[i][j] >= 0) {
                    maxgt[i][j] = Math.max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j];
                    minlt[i][j] = Math.min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j];
                } else {
                    maxgt[i][j] = Math.min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j];
                    minlt[i][j] = Math.max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j];
                }
            }
        }
        if (maxgt[m - 1][n - 1] < 0) {
            return -1;
        } else {
            return (int) (maxgt[m - 1][n - 1] % MOD);
        }
    }
}

01背包

洛谷P1048题-采药

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读入总时间 T 和草药数量 M
        int T = scanner.nextInt();
        int M = scanner.nextInt();
        
        int[] times = new int[M];
        int[] values = new int[M];
        
        // 读入每株草药的采集时间和价值
        for (int i = 0; i < M; i++) {
            times[i] = scanner.nextInt();
            values[i] = scanner.nextInt();
        }
        
        // 定义 dp 数组，dp[j] 表示在时间 j 内能够采集的最大价值
        int[] dp = new int[T + 1];
        
        // 遍历每一株草药
        for (int i = 0; i < M; i++) {
            // 从 T 到 times[i] 倒序遍历
            for (int j = T; j >= times[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - times[i]] + values[i]);
            }
        }
        
        // 输出在规定时间内可以采集到的最大总价值
        System.out.println(dp[T]);
    }
}