day45 算法训练｜动态规划 part07

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];
    }
}