和小于或等于给定数的二维数组中的最大代价值

Question

给定一个2D数组和一个数字k。

问题：我们有一个矩阵cost[][]，矩阵的每个单元格表示遍历该单元格的成本。我们从左上角(0,0)开始，我们必须到达最后一个单元格（右下角）。我必须编写一个函数，返回到达(m，n)而不超过k的最大代价路径的代价。

如果找不到最大和小于或等于k的路径，则返回-1，矩阵的值不能为负

解决方案：我尝试了很多代码，但没有一个返回我期望的结果。

我的第一个解决方案是在一个简单的数组中转换2D数组，并应用背包算法，但它不起作用，因为逻辑上没有遵循路径。（练习的逻辑随着这个想法消失了）

    if we had this 3*3 matrix:
    cost[][] = {{2,3,1}, {6,1,9},{8,2,3}}
    and k = 7

答案应该是6:(0,0)->(1,1)->(3,3)

Answer 1

如果我们把它看作是在从结束到开始的过程中减去成本，寻找最小的剩余非负量，那么一个幼稚的重复可能是如下所示。回忆录递归有时比k全维度上的迭代更适合，因为许多输入可以产生特殊的和集。

function g(m, K, i, j, k, memo){
  if (k < 0 || i < 0 || j < 0)
    return K + 1;

  if (i == 0 && j == 0)
    return k >= m[i][j] ? k - m[i][j] : K + 1;
    
  const key = String([i, j, k]);
  
  if (memo.hasOwnProperty(key))
    return memo[key];
    
  return memo[key] = Math.min(
    g(m, K, i-1, j, k - m[i][j], memo),
    g(m, K, i, j-1, k - m[i][j], memo),
    g(m, K, i-1, j-1, k - m[i][j], memo)
  )
}

function f(m, k){
  return k - g(m, k, m.length-1, m[0].length-1, k, {});
}

var m = [
  [2,3,1],
  [6,1,9],
  [8,2,3]
];

var k = 7;

console.log(f(m, k));