洛谷 P4719 【模板】动态dp【动态dp】

这道题是一道比较经典的动态规划题目，其实就是一道背包问题。下面简单介绍一下动态规划的思路。

设 $dp[i][j]$ 表示前 $i$ 个物品放入容量为 $j$ 的背包中能得到的最大价值。则状态转移方程为：

$$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])$$

其中 $v[i]$ 表示第 $i$ 个物品的体积，$w[i]$ 表示第 $i$ 个物品的价值。如果第 $i$ 个物品放不下，则 $dp[i][j] = dp[i-1][j]$。

根据状态转移方程，我们可以写出如下的代码：

int dp[N][V];
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= V; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= v[i]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+w[i]);
        }
    }
}

其中 $n$ 表示物品数量，$V$ 表示背包容量，$v[i]$ 和 $w[i]$ 分别表示第 $i$ 个物品的体积和价值。

最终答案即为 $dp[n][V]$。

相关问题

洛谷p1002过河卒java动态规划

洛谷p1002过河卒是一道动态规划问题，题目要求在一个棋盘上，卒从起点出发，不能经过马的控制点，到达终点的所有路径数。以下是Java实现的动态规划解法：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();
        int[][] horse = new int[22][22];
        int[][] dp = new int[22][22];
        horse[x1][y1] = 1;
        dp[x1][y1] = 1;
        if (x1 - 1 >= 0 && y1 - 2 >= 0) horse[x1 - 1][y1 - 2] = 1;
        if (x1 - 2 >= 0 && y1 - 1 >= 0) horse[x1 - 2][y1 - 1] = 1;
        if (x1 - 2 >= 0 && y1 + 1 <= 20) horse[x1 - 2][y1 + 1] = 1;
        if (x1 - 1 >= 0 && y1 + 2 <= 20) horse[x1 - 1][y1 + 2] = 1;
        if (x1 + 1 <= 20 && y1 + 2 <= 20) horse[x1 + 1][y1 + 2] = 1;
        if (x1 + 2 <= 20 && y1 + 1 <= 20) horse[x1 + 2][y1 + 1] = 1;
        if (x1 + 2 <= 20 && y1 - 1 >= 0) horse[x1 + 2][y1 - 1] = 1;
        if (x1 + 1 <= 20 && y1 - 2 >= 0) horse[x1 + 1][y1 - 2] = 1;
        for (int i = x1 + 1; i <= x2; i++) {
            for (int j = y1; j <= y2; j++) {
                if (horse[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        System.out.println(dp[x2][y2]);
    }
}

动态规划创建dp数组大小

动态规划中创建dp数组的大小取决于问题的特性和所需的状态数量。一般来说，dp数组的大小取决于问题的输入规模。

例如，对于一个长度为n的数组，如果我们只需要存储每个位置的最大值，那么dp数组的大小可以设为n。如果我们需要存储每个位置的最长递增子序列长度，那么dp数组的大小也可以设为n。

在某些情况下，dp数组的大小可能会更大。例如，对于一个二维网格问题，如果我们需要存储每个位置的最小路径和，那么dp数组的大小可以设为网格的行数和列数。

总之，创建dp数组的大小应该根据具体问题要求进行调整。在实际应用中，根据问题特性和算法设计的需要，确定dp数组的大小是一项重要的任务。