茄子科技 笔试题

算法小白 求解答

只有一道编程题：

1. 一个n*m数组，数组每个元素有对应的值 从0,0 走到->n-1,m-1 求走到终点路径里数组的值相加最小的和；

不太会用动态规划，我直接递归暴力的，但是超时了想加一个备忘录剪枝 但是没加对，最后只能超时提交了，有大佬能解答一下怎么加备忘录吗 或者 动态规划怎么做 万分感谢！！！！！！！！！！！！！！

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] nums = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nums[i][j] = scanner.nextInt();
            }
        }
        System.out.println(dp(nums, 0, 0));
    }

    static int dp(int[][] num,int i,int j){
        if(i == num.length-1 && j == num[0].length -1 ){
            return num[i][j];
        }else if(i == num.length - 1){
            return dp(num,i,j+1) + num[i][j];
        } else if(j == num[0].length - 1){
            return dp(num,i+1,j) + num[i][j];
        }
        return Math.min(dp(num,i+1,j)+num[i][j],dp(num,i,j+1)+num[i][j]);
    }
}

加了备忘录 之后 made 现在加上备忘录居然好使了 开始得时候还剩3分钟太着急了 可能没写对

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[][] memo;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] nums = new int[n][m];
        memo = new int[n][m];
        for(int[] tmp : memo){
            Arrays.fill(tmp,-1);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nums[i][j] = scanner.nextInt();
            }
        }
        System.out.println(dp(nums, 0, 0));
    }

    static int dp(int[][] num,int i,int j){
        if(i == num.length-1 && j == num[0].length -1 ){
            memo[i][j] = num[i][j];
            return memo[i][j];
        }
        if(memo[i][j] != -1)
            return memo[i][j];
        if(i == num.length - 1){
            memo[i][j] = dp(num,i,j+1) + num[i][j];
            return memo[i][j];
        }
        if(j == num[0].length - 1){
            memo[i][j] = dp(num,i+1,j) + num[i][j];
            return memo[i][j];
        }
        memo[i][j] = Math.min(dp(num,i+1,j)+num[i][j],dp(num,i,j+1)+num[i][j]);
        return memo[i][j];
    }
}