二维dp1

package com.zhang.reflection.面试.算法模版.动态规划;
import java.util.Arrays;
import java.util.Scanner;
/**
 * 小红拿到了一个数组，她想取一些数使得取的数之和尽可能大，但要求这个和必须是 k\k  的倍数。
 * 你能帮帮她吗？
 *
 * 第一行输入两个正整数 n\n  和 k\k
 * 第二行输入 n\n  个正整数 a_i\a
 * i
 *
 * 1<= n, k <= 10^3  1≤n,k≤10
 * 3
 *
 * 1 <= a_i <= 10^10  1≤a_i≤10^10
 *
 * 5 5
 * 4 8 2 9 1
 *
 * 20
 */
public class 二维dp1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        long[] arr=new long[n+1];
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextLong();
        }
        //dp数组，dp[i][j]表示前i个数中除以k的余数为j的当前最大和
        long[][] dp=new long[n+1][k];
        for(int i=0;i<=n;i++){
            Arrays.fill(dp[i],Long.MIN_VALUE);
        }
        //状态初始化，0个数时，最大和必为0
        dp[0][0]=0;

        for(int i=1;i<=n;i++){
            for(int j=0;j<k;j++){
                /*如果前一个状态余数为j，则更新当前余数为(j+arr[i])%k的情况，要么从余数为j的状态转化过来，
                要么前一个状态余数也是(j+arr[i])%k，即不选择当前元素*/
              //这里不太好理解，把j=0带进去看就好理解了，当前的余数为(j+arr[i])%k的最大值的状态，可以从前一个的相同余数转移过来，或者从前一个余数为j与arr[i]的和余数为(j+arr[i])%k的状态转移过来，两者取最大值即可。
                dp[i][(int)((j+arr[i])%k)]=Math.max(dp[i-1][j]+arr[i],dp[i-1][(int)((j+arr[i])%k)]);
            }
        }

        //如果小于等于0，说明不能由初始状态转化过来，没有合法方案
        if(dp[n][0]<=0){
            System.out.println(-1);
        }
        else{
            System.out.println(dp[n][0]);
        }
    }
}