1.每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素;
2.每次取走的各个元素只能是该元素所在行的行首或行尾;
3.每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值 * 2i,其中i表示第 i 次取数(从1开始编号);
4.游戏结束总得分为 m 次取数得分之和。
帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。
数据范围: ,矩阵中的值满足 ,由于得分可能会非常大,所以把值对 取模
[[1,2,3],[3,4,2]]
82
第1次:第1行取行首元素,第2行取行尾元素,本次得分为1 * 21 + 2 * 21 = 6
第2次:两行均取行首元素,本次得分为2 * 22 + 3 * 22 = 20第3次:得分为3 * 23 + 4 * 23 = 56。总得分为6 + 20 + 56 = 82
[[4,5,0,5]]
122
[[96,56,54,46,86,12,23,88,80,43],[16,95,18,29,30,53,88,83,64,67]]
316994
import java.util.*; import java.math.BigInteger; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix int整型ArrayList<ArrayList<>> * @return int整型 */ int mod=(int)1e9+7; BigInteger bigIntMod=BigInteger.valueOf(mod); int process(List<Integer> list,BigInteger[] pow){ int n=list.size(); BigInteger[][] dp=new BigInteger[n][n]; for(int i=0;i<n;i++){ dp[i][i]=BigInteger.valueOf(list.get(i)).multiply(pow[n]); } for(int i=n-2;i>=0;i--){ for(int j=i+1;j<n;j++){ int k=n-j+i; BigInteger l=dp[i][j-1].add(pow[k].multiply(BigInteger.valueOf(list.get(j)))); BigInteger r=dp[i+1][j].add(pow[k].multiply(BigInteger.valueOf(list.get(i)))); if(l.compareTo(r)<0){ dp[i][j]=r; }else{ dp[i][j]=l; } } } return dp[0][n-1].mod(bigIntMod).intValue(); } public int matrixScore (ArrayList<ArrayList<Integer>> matrix) { // write code here int res=0; int n = matrix.size(); n=matrix.get(0).size(); BigInteger[] pow=new BigInteger[n+1]; pow[0]=new BigInteger("1"); BigInteger base=BigInteger.valueOf(2); for(int i=1;i<=n;i++){ pow[i]=pow[i-1].multiply(base); } for(int i=0;i<matrix.size();i++){ res=(res+process(matrix.get(i),pow))%mod; } return res; } }
思路:
// 由于row行数据之间的计算相互独立,可以看成row次单行的计算 function matrixScore(matrix) { let n = matrix.length let m = matrix[0].length // dp[i][j] 表示对于剩余[i,j]数据,可能获取的最大值 let dp = new Array(m + 1).fill(0).map(i => new Array(m + 1).fill(0)) const MOD = 1e9 + 7 let res = 0 for (let row = 0; row < n; row++) { for (let j = 0; j < m; j++) { // 仅剩[j,j]这一个数据,获取最大值只能是如下:(1 << n) 表示 2**n dp[j][j] = ((1 << m) * matrix[row][j]); } for (let len = 1; len < m; len++) { for (let i = 0; i < m - len; i++) { let j = i + len dp[i][j] = Math.max(dp[i + 1][j] + matrix[row][i] * (1 << (m - len)), dp[i][j - 1] + matrix[row][j] * (1 << (m - len))) } } res = (res + (dp[0][m - 1] % MOD)) % MOD } return res }