动态规划
动态规划很简单,找好递推公式,把所有情况从头便利到最大即可,很简单不要怕!
步骤:
- 确定dp数组及下标含义
- 确定递推公式
☆往前面找关系
- dp数组的初始化(dp数组一般要大一号,由于初始化边界)
- 遍历
【动态规划】01背包问题(通俗易懂,超基础讲解)_动态规划算法背包问题_Yngz_Miao的博客-CSDN博客 (opens new window)
int bagV = 8; //背包大小
int[][] dp = new int[5][9]; //动态规划表 初始值全为0, { { 0 } }
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= bagV; j++) {
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
荣耀笔试: 一个商品完全等价兑换多个商品,兑换后的商品最少数量? 如10 (3,2,5) 输出2,因为5 5
int[] dp = new int[money + 1];
Arrays.fill(dp,1000);//不要用Integer.MAX_VALUE,取个适合的大数,加1不为负数都行,Integer.MAX_VALUE-1都行
dp[0] = 0;
for (int value : array) {//这两个循环谁前后都一样
for (int j = 1; j <=money; j++) {
if(j>=value) dp[j] = Math.min(dp[j], dp[j - value] + 1);//因为取最小值
}
}
System.out.println(dp[money] == 1000 ? -1 : dp[money]);
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
编辑 (opens new window)
上次更新: 2023/05/26, 15:58:27