我将如何使用 DP 解决这个问题？
How will I solve this using DP?
问题link：http://codeforces.com/contest/2/problem/B
有一个方阵n⟩×⟩n，由非负整数组成。你应该在上面找到这样的方法
从矩阵的左上角单元格开始；
每个后续单元格都在当前单元格的右侧或下方；
这条路在右下角的单元格结束。
而且，如果我们把一路上的所有数字相乘，结果应该是最少的"round"。换句话说，它应该以尽可能少的零结尾。
输入
第一行包含一个整数n（2⟩≤⟩n⟩≤⟩1000），n是矩阵的大小。然后跟随包含矩阵元素的n行（不超过10^9的非负整数）。
输出
在第一行打印最少数量的尾随零。在第二行打印相应的方式本身。
我想到了以下几点： 最后，无论答案是什么，它都应该包含最小的 2 和 5 的幂。因此，我所做的是，对于输入矩阵中的每个条目，我计算了 2 和 5 的幂并将它们存储在单独的矩阵中。
for (i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
cin>>foo;
matrix[i][j] = foo;
int n1 = calctwo(foo); // calculates the number of 2's in factorisation of that number
int n2 = calcfive(foo); // calculates number of 5's
two[i][j] = n1;
five[i][j] = n2;
}
}
之后，我这样做了：
for (i = 0; i < n; i++)
{
for ( j = 0; j < n; j++ )
{
dp[i][j] = min(two[i][j],five[i][j]); // Here, dp[i][j] will store minimum number of 2's and 5's.
}
}
但以上并不是一个有效的答案，我不知道为什么？我是否实施了正确的方法？或者，这是正确的解法吗？
编辑：这是我计算一个数中二的个数和五的个数的函数。
int calctwo (int foo)
{
int counter = 0;
while (foo%2 == 0)
{
if (foo%2 == 0)
{
counter++;
foo = foo/2;
}
else
break;
}
return counter;
}
int calcfive (int foo)
{
int counter = 0;
while (foo%5 == 0)
{
if (foo%5 == 0)
{
counter++;
foo = foo/5;
}
else
break;
}
return counter;
}
Edit2: I/O link:
中给出的示例
输入：
3
1 2 3
4 5 6
7 8 9
输出：
0
DDRR
这是代码。我使用 pair<int,int> 在矩阵中存储因子 2 和 5。
#include<vector>
#include<iostream>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define MP make_pair
int calc2(int a){
int c=0;
while(a%2==0){
c++;
a/=2;
}
return c;
}
int calc5(int a){
int c=0;
while(a%5==0){
c++;
a/=5;
}
return c;
}
int mini(int a,int b){
return a<b?a:b;
}
pii min(pii a, pii b){
if(mini(a.F,a.S) < mini(b.F,b.S))
return a;
return b;
}
int main(){
int n;
cin>>n;
vector<vector<pii > > v;
vector<vector<int> > path;
int i,j;
for(i=0;i<n;i++){
vector<pii > x;
vector<int> q(n,0);
for(j=0;j<n;j++){
int y;cin>>y;
x.push_back(MP(calc2(y),calc5(y))); //I store factors of 2,5 in the vector to calculate
}
x.push_back(MP(100000,100000)); //padding each row to n+1 elements (to handle overflow in code)
v.push_back(x);
path.push_back(q); //initialize path matrix to 0
}
vector<pii > x(n+1,MP(100000,100000));
v.push_back(x); //pad 1 more row to handle index overflow
for(i=n-1;i>=0;i--){
for(j=n-1;j>=0;j--){ //move from destination to source grid
if(i==n-1 && j==n-1)
continue;
//here, the LHS of condition in if block is the condition which determines minimum number of trailing 0's. This is the same condition that is used to manipulate "v" for getting the same result.
if(min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S)) == MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S))
path[i][j] = 1; //go down
else
path[i][j] = 2; //go right
v[i][j] = min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S));
}
}
cout<<mini(v[0][0].F, v[0][0].S)<<endl; //print result
for(i=0,j=0;i<=n-1 && j<=n-1;){ //print path (I don't know o/p format)
cout<<"("<<i<<","<<j<<") -> ";
if(path[i][j]==1)
i++;
else
j++;
}
return 0;
}
就我检查的测试用例而言，这段代码给出了很好的结果。如果您对此代码有任何疑问，请在评论中提问。
编辑：
基本的思维过程。
要到达目的地，只有两种选择。我从目的地开始，以避免提前计算的问题，因为如果 2 个具有相同的最小值，那么我们选择其中一个。如果到目的地的路径已经计算好了，我们走哪条路都没有关系。
最起码要检查哪一对更合适。如果一对中的 2 或 5 最少，则它产生的 0 会更少。
这是一个使用Javascript 和函数式编程的解决方案。
它依赖于几个函数：
- 核心函数是
smallest_trailer递归遍历网格。我选择了 4 个可能的方向，左 "L"、右 "R"、下 "D" 和 "U"。不可能在同一个细胞上传递两次。选择的方向是尾随零数最少的方向。尾随零的计数专门用于另一个功能。
- 函数
zero_trailer(p,n,nbz) 假定您到达一个具有值 p 的单元格，而您已经有一个累加器 n 并且在途中遇到 nbz 个零。函数 returns 一个包含两个元素的数组，新的零数和新的累加器。累加器将是 2 或 5 的幂。函数使用辅助函数 pow_2_5(n) 即 returns 在 n. 中的 2 和 5 的幂
- 其他函数更有趣：
deepCopy(arr) 对数组 arr、out_bound(i,j,n) 进行标准深度复制 returns 如果单元格 (i,j) 是超出大小为 n、myMinIndex(arr) returns 二维数组的最小索引的网格（每个子数组包含尾随零的 nb 和作为字符串的路径） .最小值仅取自子数组的第一个元素。
MAX_SAFE_INTEGER 是一个（大）常量，表示路径错误时尾随零的最大数量（例如超出范围）。
这是代码，它适用于上面评论中给出的示例和原始 link。
var MAX_SAFE_INTEGER = 9007199254740991;
function pow_2_5(n) {
// returns the power of 2 and 5 inside n
function pow_not_2_5(k) {
if (k%2===0) {
return pow_not_2_5(k/2);
}
else if (k%5===0) {
return pow_not_2_5(k/5);
}
else {
return k;
}
}
return n/pow_not_2_5(n);
}
function zero_trailer(p,n,nbz) {
// takes an input two numbers p and n that should be multiplied and a given initial number of zeros (nbz = nb of zeros)
// n is the accumulator of previous multiplications (a power of 5 or 2)
// returns an array [kbz, k] where kbz is the total new number of zeros (nbz + the trailing zeros from the multiplication of p and n)
// and k is the new accumulator (typically a power of 5 or 2)
function zero_aux(k,kbz) {
if (k===0) {
return [1,0];
}
else if (k%10===0) {
return zero_aux(k/10,kbz+1);
}
else {
return [kbz,k];
}
}
return zero_aux(pow_2_5(p)*n,nbz);
}
function out_bound(i,j,n) {
return !((i>=0)&&(i<n)&&(j>=0)&&(j<n));
}
function deepCopy(arr){
var toR = new Array(arr.length);
for(var i=0;i<arr.length;i++){
var toRi = new Array(arr[i].length);
for(var j=0;j<arr[i].length;j++){
toRi[j] = arr[i][j];
}
toR[i] = toRi;
}
return toR;
}
function myMinIndex(arr) {
var min = arr[0][0];
var minIndex = 0;
for (var i = 1; i < arr.length; i++) {
if (arr[i][0] < min) {
minIndex = i;
min = arr[i][0];
}
}
return minIndex;
}
function smallest_trailer(grid) {
var n = grid.length;
function st_aux(i,j,grid_aux, acc_mult, nb_z, path) {
if ((i===n-1)&&(j===n-1)) {
var tmp_acc_nbz_f = zero_trailer(grid_aux[i][j],acc_mult,nb_z);
return [tmp_acc_nbz_f[0], path];
}
else if (out_bound(i,j,n)) {
return [MAX_SAFE_INTEGER,[]];
}
else if (grid_aux[i][j]<0) {
return [MAX_SAFE_INTEGER,[]];
}
else {
var tmp_acc_nbz = zero_trailer(grid_aux[i][j],acc_mult,nb_z) ;
grid_aux[i][j]=-1;
var res = [st_aux(i+1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"D"),
st_aux(i-1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"U"),
st_aux(i,j+1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"R"),
st_aux(i,j-1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"L")];
return res[myMinIndex(res)];
}
}
return st_aux(0,0,grid, 1, 0, "");
}
myGrid = [[1, 25, 100],[2, 1, 25],[100, 5, 1]];
console.log(smallest_trailer(myGrid)); //[0,"RDDR"]
myGrid = [[1, 2, 100],[25, 1, 5],[100, 25, 1]];
console.log(smallest_trailer(myGrid)); //[0,"DRDR"]
myGrid = [[1, 10, 1, 1, 1],[1, 1, 1, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1]];
console.log(smallest_trailer(myGrid)); //[0,"DRRURRDDDD"]
由于您只对尾随零的数量感兴趣，因此您只需考虑 2、5 的幂，您可以将它们保存在两个单独的 nxn 数组中。所以对于数组
1 2 3
4 5 6
7 8 9
你只保留数组
the powers of 2 the powers of 5
0 1 0 0 0 0
2 0 1 0 1 0
0 3 0 0 0 0
问题的见解如下。请注意，如果您找到使 2 的幂之和最小化的路径和使 5 的幂数之和最小化的路径，那么答案就是这两条路径中具有较低值的路径。因此，您将问题简化为以下经典 dp 问题的两次应用：找到一条路径，从左上角开始到右下角结束，使其元素之和最小。同样，按照示例，我们有：
minimal path for the
powers of 2 value
* * - 2
- * *
- - *
minimal path for the
powers of 5 value
* - - 0
* - -
* * *
所以你的答案是
* - -
* - -
* * *
价值0
注1
似乎取两条最优路径中的最小值只给出了一个上限，所以可能会出现一个问题：这个界限是否真的达到了？答案是肯定的。为方便起见，设2的最优路径上2的个数为a，5的最优路径上5的个数为b。在不失一般性的情况下，假设两条最佳路径中的最小值是 2 的幂（即 a < b）。令最小路径上 5 的个数为 c。现在的问题是：这条路径上的 5 是否与 2 一样多（即 c >= a？）。假设答案是否定的。这意味着沿着最小路径（即 c < a），5 比 2 少。由于 5 的路径的最优值是 b，我们得到每个 5 的路径至少有 b 个 5。对于最小路径也应该如此。这意味着 c > b。我们有 c < a 所以 a > b 但最初的假设是 a < b。矛盾。
注2
您可能还想考虑矩阵中有一个元素 0 的情况。我假设乘积为 1 时尾随零的数量。在这种情况下，如果算法产生的结果的值大于 1，则应输出 1 并打印通过元素 0 的路径.
这是我的动态规划解决方案。
https://app.codility.com/demo/results/trainingAXFQ5B-SZQ/
为了更好地理解我们可以简化任务并假设矩阵中没有零（即矩阵只包含正整数），那么 Java 解决方案如下：
class Solution {
public int solution(int[][] a) {
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
return min(minPws2, minPws5);
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pws(a[i][j], p);
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
//Only when n > 0
int pws = 0;
while (n % p == 0) {
pws++;
n /= p;
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
问题link：http://codeforces.com/contest/2/problem/B
有一个方阵n⟩×⟩n，由非负整数组成。你应该在上面找到这样的方法
从矩阵的左上角单元格开始； 每个后续单元格都在当前单元格的右侧或下方； 这条路在右下角的单元格结束。 而且，如果我们把一路上的所有数字相乘，结果应该是最少的"round"。换句话说，它应该以尽可能少的零结尾。
输入 第一行包含一个整数n（2⟩≤⟩n⟩≤⟩1000），n是矩阵的大小。然后跟随包含矩阵元素的n行（不超过10^9的非负整数）。
输出 在第一行打印最少数量的尾随零。在第二行打印相应的方式本身。
我想到了以下几点： 最后，无论答案是什么，它都应该包含最小的 2 和 5 的幂。因此，我所做的是，对于输入矩阵中的每个条目，我计算了 2 和 5 的幂并将它们存储在单独的矩阵中。
for (i = 0; i < n; i++)
{
for ( j = 0; j < n; j++)
{
cin>>foo;
matrix[i][j] = foo;
int n1 = calctwo(foo); // calculates the number of 2's in factorisation of that number
int n2 = calcfive(foo); // calculates number of 5's
two[i][j] = n1;
five[i][j] = n2;
}
}
之后，我这样做了：
for (i = 0; i < n; i++)
{
for ( j = 0; j < n; j++ )
{
dp[i][j] = min(two[i][j],five[i][j]); // Here, dp[i][j] will store minimum number of 2's and 5's.
}
}
但以上并不是一个有效的答案，我不知道为什么？我是否实施了正确的方法？或者，这是正确的解法吗？
编辑：这是我计算一个数中二的个数和五的个数的函数。
int calctwo (int foo)
{
int counter = 0;
while (foo%2 == 0)
{
if (foo%2 == 0)
{
counter++;
foo = foo/2;
}
else
break;
}
return counter;
}
int calcfive (int foo)
{
int counter = 0;
while (foo%5 == 0)
{
if (foo%5 == 0)
{
counter++;
foo = foo/5;
}
else
break;
}
return counter;
}
Edit2: I/O link:
中给出的示例输入：
3
1 2 3
4 5 6
7 8 9
输出：
0
DDRR
这是代码。我使用 pair<int,int> 在矩阵中存储因子 2 和 5。
#include<vector>
#include<iostream>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define MP make_pair
int calc2(int a){
int c=0;
while(a%2==0){
c++;
a/=2;
}
return c;
}
int calc5(int a){
int c=0;
while(a%5==0){
c++;
a/=5;
}
return c;
}
int mini(int a,int b){
return a<b?a:b;
}
pii min(pii a, pii b){
if(mini(a.F,a.S) < mini(b.F,b.S))
return a;
return b;
}
int main(){
int n;
cin>>n;
vector<vector<pii > > v;
vector<vector<int> > path;
int i,j;
for(i=0;i<n;i++){
vector<pii > x;
vector<int> q(n,0);
for(j=0;j<n;j++){
int y;cin>>y;
x.push_back(MP(calc2(y),calc5(y))); //I store factors of 2,5 in the vector to calculate
}
x.push_back(MP(100000,100000)); //padding each row to n+1 elements (to handle overflow in code)
v.push_back(x);
path.push_back(q); //initialize path matrix to 0
}
vector<pii > x(n+1,MP(100000,100000));
v.push_back(x); //pad 1 more row to handle index overflow
for(i=n-1;i>=0;i--){
for(j=n-1;j>=0;j--){ //move from destination to source grid
if(i==n-1 && j==n-1)
continue;
//here, the LHS of condition in if block is the condition which determines minimum number of trailing 0's. This is the same condition that is used to manipulate "v" for getting the same result.
if(min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S)) == MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S))
path[i][j] = 1; //go down
else
path[i][j] = 2; //go right
v[i][j] = min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S));
}
}
cout<<mini(v[0][0].F, v[0][0].S)<<endl; //print result
for(i=0,j=0;i<=n-1 && j<=n-1;){ //print path (I don't know o/p format)
cout<<"("<<i<<","<<j<<") -> ";
if(path[i][j]==1)
i++;
else
j++;
}
return 0;
}
就我检查的测试用例而言，这段代码给出了很好的结果。如果您对此代码有任何疑问，请在评论中提问。
编辑：
基本的思维过程。
要到达目的地，只有两种选择。我从目的地开始，以避免提前计算的问题，因为如果 2 个具有相同的最小值，那么我们选择其中一个。如果到目的地的路径已经计算好了，我们走哪条路都没有关系。
最起码要检查哪一对更合适。如果一对中的 2 或 5 最少，则它产生的 0 会更少。
这是一个使用Javascript 和函数式编程的解决方案。 它依赖于几个函数：
- 核心函数是
smallest_trailer递归遍历网格。我选择了 4 个可能的方向，左 "L"、右 "R"、下 "D" 和 "U"。不可能在同一个细胞上传递两次。选择的方向是尾随零数最少的方向。尾随零的计数专门用于另一个功能。 - 函数
zero_trailer(p,n,nbz)假定您到达一个具有值p的单元格，而您已经有一个累加器n并且在途中遇到nbz个零。函数 returns 一个包含两个元素的数组，新的零数和新的累加器。累加器将是 2 或 5 的幂。函数使用辅助函数pow_2_5(n)即 returns 在n. 中的 2 和 5 的幂
- 其他函数更有趣：
deepCopy(arr)对数组arr、out_bound(i,j,n)进行标准深度复制 returns 如果单元格(i,j)是超出大小为n、myMinIndex(arr)returns 二维数组的最小索引的网格（每个子数组包含尾随零的 nb 和作为字符串的路径） .最小值仅取自子数组的第一个元素。 MAX_SAFE_INTEGER是一个（大）常量，表示路径错误时尾随零的最大数量（例如超出范围）。
这是代码，它适用于上面评论中给出的示例和原始 link。
var MAX_SAFE_INTEGER = 9007199254740991;
function pow_2_5(n) {
// returns the power of 2 and 5 inside n
function pow_not_2_5(k) {
if (k%2===0) {
return pow_not_2_5(k/2);
}
else if (k%5===0) {
return pow_not_2_5(k/5);
}
else {
return k;
}
}
return n/pow_not_2_5(n);
}
function zero_trailer(p,n,nbz) {
// takes an input two numbers p and n that should be multiplied and a given initial number of zeros (nbz = nb of zeros)
// n is the accumulator of previous multiplications (a power of 5 or 2)
// returns an array [kbz, k] where kbz is the total new number of zeros (nbz + the trailing zeros from the multiplication of p and n)
// and k is the new accumulator (typically a power of 5 or 2)
function zero_aux(k,kbz) {
if (k===0) {
return [1,0];
}
else if (k%10===0) {
return zero_aux(k/10,kbz+1);
}
else {
return [kbz,k];
}
}
return zero_aux(pow_2_5(p)*n,nbz);
}
function out_bound(i,j,n) {
return !((i>=0)&&(i<n)&&(j>=0)&&(j<n));
}
function deepCopy(arr){
var toR = new Array(arr.length);
for(var i=0;i<arr.length;i++){
var toRi = new Array(arr[i].length);
for(var j=0;j<arr[i].length;j++){
toRi[j] = arr[i][j];
}
toR[i] = toRi;
}
return toR;
}
function myMinIndex(arr) {
var min = arr[0][0];
var minIndex = 0;
for (var i = 1; i < arr.length; i++) {
if (arr[i][0] < min) {
minIndex = i;
min = arr[i][0];
}
}
return minIndex;
}
function smallest_trailer(grid) {
var n = grid.length;
function st_aux(i,j,grid_aux, acc_mult, nb_z, path) {
if ((i===n-1)&&(j===n-1)) {
var tmp_acc_nbz_f = zero_trailer(grid_aux[i][j],acc_mult,nb_z);
return [tmp_acc_nbz_f[0], path];
}
else if (out_bound(i,j,n)) {
return [MAX_SAFE_INTEGER,[]];
}
else if (grid_aux[i][j]<0) {
return [MAX_SAFE_INTEGER,[]];
}
else {
var tmp_acc_nbz = zero_trailer(grid_aux[i][j],acc_mult,nb_z) ;
grid_aux[i][j]=-1;
var res = [st_aux(i+1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"D"),
st_aux(i-1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"U"),
st_aux(i,j+1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"R"),
st_aux(i,j-1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"L")];
return res[myMinIndex(res)];
}
}
return st_aux(0,0,grid, 1, 0, "");
}
myGrid = [[1, 25, 100],[2, 1, 25],[100, 5, 1]];
console.log(smallest_trailer(myGrid)); //[0,"RDDR"]
myGrid = [[1, 2, 100],[25, 1, 5],[100, 25, 1]];
console.log(smallest_trailer(myGrid)); //[0,"DRDR"]
myGrid = [[1, 10, 1, 1, 1],[1, 1, 1, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1]];
console.log(smallest_trailer(myGrid)); //[0,"DRRURRDDDD"]
由于您只对尾随零的数量感兴趣，因此您只需考虑 2、5 的幂，您可以将它们保存在两个单独的 nxn 数组中。所以对于数组
1 2 3
4 5 6
7 8 9
你只保留数组
the powers of 2 the powers of 5
0 1 0 0 0 0
2 0 1 0 1 0
0 3 0 0 0 0
问题的见解如下。请注意，如果您找到使 2 的幂之和最小化的路径和使 5 的幂数之和最小化的路径，那么答案就是这两条路径中具有较低值的路径。因此，您将问题简化为以下经典 dp 问题的两次应用：找到一条路径，从左上角开始到右下角结束，使其元素之和最小。同样，按照示例，我们有：
minimal path for the
powers of 2 value
* * - 2
- * *
- - *
minimal path for the
powers of 5 value
* - - 0
* - -
* * *
所以你的答案是
* - -
* - -
* * *
价值0
注1
似乎取两条最优路径中的最小值只给出了一个上限，所以可能会出现一个问题：这个界限是否真的达到了？答案是肯定的。为方便起见，设2的最优路径上2的个数为a，5的最优路径上5的个数为b。在不失一般性的情况下，假设两条最佳路径中的最小值是 2 的幂（即 a < b）。令最小路径上 5 的个数为 c。现在的问题是：这条路径上的 5 是否与 2 一样多（即 c >= a？）。假设答案是否定的。这意味着沿着最小路径（即 c < a），5 比 2 少。由于 5 的路径的最优值是 b，我们得到每个 5 的路径至少有 b 个 5。对于最小路径也应该如此。这意味着 c > b。我们有 c < a 所以 a > b 但最初的假设是 a < b。矛盾。
注2
您可能还想考虑矩阵中有一个元素 0 的情况。我假设乘积为 1 时尾随零的数量。在这种情况下，如果算法产生的结果的值大于 1，则应输出 1 并打印通过元素 0 的路径.
这是我的动态规划解决方案。
https://app.codility.com/demo/results/trainingAXFQ5B-SZQ/
为了更好地理解我们可以简化任务并假设矩阵中没有零（即矩阵只包含正整数），那么 Java 解决方案如下：
class Solution {
public int solution(int[][] a) {
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
return min(minPws2, minPws5);
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pws(a[i][j], p);
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
//Only when n > 0
int pws = 0;
while (n % p == 0) {
pws++;
n /= p;
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}