Leetcode动态规划

爬楼梯

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

按着数学来看的话，就是如果是1阶梯的话，就是1

大于等于2的有两种，是i-1+(i-2)

然后我们使用记忆数组来记忆之前算过的

然后使用递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution70A{
    public int climbStairs(int n ){
        int[] memo  = new int[n+1];
        return dfs(n,memo);
    }
    private int dfs(int i,int[] memo){
        if  (i<=1){
            return 1;
        }
        if  (memo[i]!=0){
            return memo[i];
        }
        return memo[i] = dfs(i-1,memo)+dfs(i-2,memo);
    }

}

遇到记忆数组不是1的，调用记忆数组，为0的就直接计算

这样就不会超时

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution746{
    public int minCostClimbingStairs(int[] cost){
        int n = cost.length;
        int [] memo = new int [n+1];
        Arrays.fill(memo,-1);
        return dfs(n,memo,cost);
    }
    private int dfs(int i ,int[] memo,int[] cost){
        if (i<=1){
            return 0;
        }
        if (memo[i]!=-1){
            return memo[i];
        }
        int res1 = dfs(i-1,memo,cost)+cost[i-1];
        int res2 = dfs(i-2,memo,cost)+cost[i-2];
        return memo[i] = Math.min(res2,res1);
    }
}

跟上面那个题一样，只不过最后取的时候，是看花费哪个少了

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

本质还是爬楼梯问题啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution377{
    public int combinationSum4(int[] nums, int target){
        int[] memo = new int[target+1];
        Arrays.fill(memo,-1);
        return dfs(target,nums,memo);
    }
    private int dfs(int i,int[] nums,int[] memo){
        if (i==0) return 1;
        if (memo[i]!=-1){
            return memo[i];
        }
        int res = 0;
        for (int x:nums){
            if (x<=i){
                res +=dfs(i-x,nums,memo);
            }
        }
        return memo[i]  = res;
    }
}

也是类似的

2466. 统计构造好字符串的方案数

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

  • 将 '0' 在字符串末尾添加 zero 次。
  • 将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution2466{
    public int countGoodStrings(int low, int high, int zero, int one){
        int ans = 0;
        final int MOD = 1_000_000_007;
        int [] f = new int[high+1];
        f[0]= 1;
        for (int i=1;i<=high;i++){
            if (i>=zero) f[i] = f[i-zero];
            if (i>=one) f[i] = (f[i]+f[i-one])%MOD;
            if (i>=low) ans = (ans+f[i])%MOD;
        }
        return ans;
    }
}

使用递推

相当于把递推式 f[i]=f[i−zero]+f[i−one] 拆分成了两步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private static final int MOD = 1_000_000_007;

    public int countGoodStrings(int low, int high, int zero, int one) {
        int[] memo = new int[high + 1];
        Arrays.fill(memo, -1); // -1 表示没有计算过
        int ans = 0;
        for (int i = low; i <= high; i++) {
            ans = (ans + dfs(i, zero, one, memo)) % MOD;
        }
        return ans;
    }

    private int dfs(int i, int zero, int one, int[] memo) {
        if (i < 0) {
            return 0;
        }
        if (i == 0) {
            return 1;
        }
        if (memo[i] != -1) { // 之前计算过
            return memo[i];
        }
        return memo[i] = (dfs(i - zero, zero, one, memo) + dfs(i - one, zero, one, memo)) % MOD;
    }
}

记忆递推方法