day45 算法训练|动态规划 part07

发布时间:2023年12月22日

70. 爬楼梯(进阶版)

可以看做跟昨天的给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数看作是同一题目,两者都是无限取,且需要考虑顺序。

322. 零钱兑换

1. dp数组及含义

dp[i][j]: coins[0..i]的选择中达到jamount用的coins的最少个数

1D:dp[j]:凑足总额为j所需钱币的最少个数为dp[j]?

2.递推公式

dp[i][j] = min(dp[i-1][j],dp[i][j-coins[i]]+1)

两种状态

dp[i-1][j]:不选择第i个硬币

dp[i][j-coins[i]]+1 选择一次第i个硬币

1D:?dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3.dp数组初始化

2D:

dp[...][0]=0; 根据题目,amount为0的时候,所需钱币数为0;

其他位置由于是求最小值,需要初始化为一个最大的数(至少比result可能的最大值要大),否则就会影响递推公式的更新(实际最小值比初始化的值要大的时候:min(dp[j - coins[i]] + 1, 初始值)=初始值)

初始化为最大值也好返回-1,代表没法拼成

我的办法解决溢出:

JAVA中如果初始化为Integer.MAX_VALUE 会有整型溢出的可能性:dp[i][j-coins[i]]+1时 Interger.MAX_VALUE+1变成负数

所以可以根据题干条件设置一个不会溢出但是大于res可能的最大值的值

amount最大为10000,coin最小为1,所以res最大为10000,我们可以设置大于10000的值为初始化,比如10001

1D:dp[0]=0; 其他位置为10001 同理2D的情况

答案办法:

在递归公式计算之前;先判断dp[j - coins[i]] != max

4. 遍历顺序:

完全背包所以背包的遍历顺序为正序

对2维:循环内外顺序不影响

对1D:如果完全跟2D dp数组对应上,应该是先物品再背包 (组合)

但是由于是求最小值,跟物品顺序没有关系,所以其实对于1D,两种内外循环顺序都可行

虽然先背包循环,再物品循环,会影响到dp[j] 与dp[i][j]的互相对应关系,但是不影响最终结果,只要把整个过程遍历完了,仍然能够得到最小值。但是如果是累加(多少种方法),则要考虑内外循环顺序。

279.完全平方数

其实与322题目一样就是套用了一个完全平方数

题目转换:完全平方数就是物品(可以无限件使用),凑个正整数n就是背包,问凑满这个背包最少有多少物品?

***不可能没有解,因为1也是完全平方数,有1的话怎么样都可以拼出想要的数

正是因为如此,不需要考虑溢出,因为表格都可以计算,不可能有凑不成的情况发生

class Solution {
    // 版本一,先遍历物品, 再遍历背包
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        //初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
	//如果不想要寫for-loop填充數組的話,也可以用JAVA內建的Arrays.fill()函數。
	//Arrays.fill(dp, Integer.MAX_VALUE);
	
        //当和为0时,组合的个数为0
        dp[0] = 0;
        // 遍历物品
        for (int i = 1; i * i <= n; i++) {
            // 遍历背包
            for (int j = i * i; j <= n; j++) {
                //if (dp[j - i * i] != max) {
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
                //}
		//不需要這個if statement,因爲在完全平方數這一題不會有"湊不成"的狀況發生( 一定可以用"1"來組成任何一個n),故comment掉這個if statement。
            }
        }
        return dp[n];
    }
}

文章来源:https://blog.csdn.net/AdrianLeon/article/details/135148042
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。