线性dp

跳格子[华为]

题目描述：

每个格子有魔法值，代表可以跳得最远距离；最多可以跳 k 次，求跳到终点的最小步数；

案例：

输入:

2 1 5 6 2 3

3

输出：

2

方法一：记忆化搜索

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        powers = Arrays.stream(sc.nextLine().split(" "))
                .mapToInt(Integer::valueOf)
                .toArray();
        int n = powers.length;
        int k = sc.nextInt();
        memo = new int[n];
        Arrays.fill(memo,-1);
        int ans = dfs(0);
        if(ans<=k){
            System.out.println(ans);
        }else{
            System.out.println(-1);
        }
    }
    static int[] memo;
    static int[] powers;
    static int dfs(int i){
        // 目前位置到达终点
        if(i>=powers.length-1){
            return 0;
        }
        if(memo[i]!=-1){
            return memo[i];
        }
        int ans = Integer.MAX_VALUE;
        // 枚举在 i 位置可跳的步数
        for(int j=1;j<=powers[i];j++){
            ans = Math.min(ans,1+dfs(i+j));
        }
        return memo[i] = ans;
    }
}

方法二：动态规划

见45. 跳跃游戏 II (opens new window)

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,Integer.MAX_VALUE/2);
        dp[0] = 0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(i-j<=nums[j]){
                    dp[i] = Math.min(dp[j]+1,dp[i]);
                }
            }
        }
        return dp[n-1];
    }
}

士兵高度[联通]

**输入样例：**3 4 1 2 3 4 3 1 1 1 4 1 1 3 2 **输出样例：**4 1 2

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
      BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
      int total = Integer.valueOf(reader.readLine());
      for(int k=0;k<total;k++){
        int n = Integer.valueOf(reader.readLine());
        int[] nums = Arrays.stream(reader.readLine().split(" "))
          .mapToInt(Integer::valueOf)
          .toArray();
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        int ret = 0;
        for(int i=0;i<n;i++){
          for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
              dp[i] = Math.max(dp[j]+1,dp[i]);
            }
          }
          ret = Math.max(ret,dp[i]);
        }
        System.out.println(ret);
      }
    }
}