_57爬楼梯_第八期模拟笔试 && _322零钱兑换_无基数_记忆化搜索 &&

_57爬楼梯_第八期模拟笔试

package 代码随想录.动态规划;

import java.util.Scanner;

public class _57爬楼梯_第八期模拟笔试 {
    public static void main(String[] args) {
        /*
        题目描述:
            假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
            每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
            注意：给定 n 是一个正整数。
         */
        //TODO 以前爬楼梯的时候，都是明确告诉你，每次最多怕1,2,3阶这样，这次允许你至多爬m阶
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        climbALadder(n,m);
    }

    /**
     *
     * @param n 需要 n 阶你才能到达楼顶。
     * @param m 每次你可以爬至多m (1 <= m < n)个台阶。
     * 你有多少种不同的方法可以爬到楼顶呢？
     */
    private static void climbALadder(int n, int m) {
        int dp [] = new int[n+1];
        dp[0] = 1;
        for (int j = 1;j<=n;j++){
            for (int i=1;i<=m;i++){
                if (j-i >= 0){
                    dp[j] += dp[j-i];
                }
            }
        }
        System.out.println(dp[n]);
    }
}

_322零钱兑换_无基数_记忆化搜索

package 代码随想录.动态规划;

public class _322零钱兑换_无基数_记忆化搜索 {
    /**
     *
     * @param coins
     * @param amount
     * @return  计算并返回可以凑成总金额所需的 最少的硬币个数 。
     */
    public int coinChange(int[] coins, int amount) {
        //那么必然每次选择时，从最大的硬币开始尝试兑换
        //但是这样问题，就会出现在如果基数不是1时，那么就不一定是，每一次的从大到小的数都应该被取
        if (amount < 1){
            return 0;
        }
        return coinsFind(coins,amount,new int[amount]);
    }

    /**
     *
     * @param coins
     * @param remb
     * @param count
     * @return
     */
    private int coinsFind(int[] coins, int remb, int[] count) {
        if (remb < 0){
            return -1;
        }
        if (remb == 0){
            return 0;
        }
        if (count[remb - 1] != 0){
            return count[remb - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int coin :coins){
            int res = coinsFind(coins,remb - coin,count);
            if (res >= 0 && res < min){
                min = res+1;
            }
        }
        count[remb - 1] = (min == Integer.MAX_VALUE) ? -1 :min;
        return count[remb - 1];
    }
}

_322零钱兑换_无基数_dp

package 代码随想录.动态规划;

public class _322零钱兑换_无基数_dp {
    /**
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int [] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 0;j <dp.length;j++) {
            dp[j] = max;
        }
        //当金额为0时，需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length;i++) {
            //每次硬币的数量可以任意选择
            for (int j = coins[i];j<=amount;j++){
                //只有dp[ j-coins[i] ]不是初始最大值时，该位才有选择的必要
                if (dp[j - coins[i]] != max){
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j],dp[j-coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 :dp[amount];
    }
}

_377组合总和Ⅳ

package 代码随想录.动态规划;

public class _377组合总和Ⅳ {
    /**
     *
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        //TODO 使用nums[]中的数组元素，组合出target这一目标值，然后就是每个数可以无限次使用
        //从最大元素的最大使用次数开始，以此向下减少，直到0为止，内层套其他循环
        //但是这样势必导致超时，因此需要用dp去优化
        int dp[] = new int[target + 1];
        dp[0] = 1;
        for (int i=0;i<=target;i++){    //以选取target目标值为参考
            for (int j = 0;j< nums.length;j++){     //思考所有的选取情况
                if(i >= nums[j]){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}