动态规划算法基础及leetcode例题

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;             
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int index = 2; index <= n; index++){
            dp[index] = dp[index - 1] + dp[index - 2];
        }
        return dp[n];
    }
}

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < n; i++) {
            for(int j = target; j >= nums[i]; j--) {
                //物品 i 的重量是 nums[i]，其价值也是 nums[i]
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}

private static void testCompletePack(){
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++){ // 遍历物品
            for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                System.out.print(j + "-" +dp[j]);
                System.out.print(" ");
            }
            System.out.println();
        }
}

//输出
1-15 2-30 3-45 4-60 
3-45 4-60 
4-60 

for (int i = 0; i < weight.length; i++){ // 遍历物品
    for (int j = bagWeight; j >= weight[i]; j--){ // 遍历背包容量
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        System.out.print(j + "-" +dp[j]);
        System.out.print(" ");
     }
     System.out.println();
}

//输出
4-15 3-15 2-15 1-15 
4-35 3-20 
4-35 

class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

class Solution {
    public int combinationSum4(int[] nums, int target) {
        if(nums == null || nums.length==0) return 0;

        int[] dp = new int[target+1];
        dp[0] = 1;

        for(int j=0;j<=target;j++){
            for(int i=0;i<nums.length;i++){
                if(j>=nums[i]){
                    dp[j] += dp[j-nums[i]];
                }
            }
        }

        return dp[target];
    
    }
}

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        int[] nums = new int[]{1,2};

        dp[0]=1;

        for(int j = 0;j<=n;j++){
            for(int i=0;i<nums.length;i++){
                if(j>=nums[i]){
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[n];
    }
}