資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究到達目的地的初始最小點數
從給定網格的左上角開始，必須到達右下角。網格中的每個單元格都包含一個數字，該數字可能是正數或負數。當一個人到達一個單元格 (i, j) 時，他擁有的代幣數量可能會隨著該單元格的值而增加或減少。我們必須找到完成旅程所需的初始代幣的最小數量。
有一些規則：
- 我們可以向右或向下移動。
- 如果我們的總代幣少於 (i, j) 的值，則我們不能移動到單元格 (i, j)。
- 我們必須以最小的正點數到達目的地。
輸入和輸出
Input: The token for each room as a matrix. -2 -3 3 -5 -10 1 10 30 -5 Output: The minimum token required to start the journey. For this example, the required token is 7.
演算法
minInitTokens(matrix)
輸入：每個房間的代幣矩陣。
輸出：從起點到達目的地的最小所需代幣。
Begin define matrix minToken of size same as matrix m := number of rows in matrix n := number of columns in matrix if matrix[m-1, n-1] > 0, then minToken[m-1, n-1] := 0 else minToken[m-1, n-1] := 1 + absolute value of matrix[m-1, n-1] for i := m-2 down to 0, do minToken[i, n-1] := maximum of 1 and (minToken[i+1, n-1]-matrix[i,n-1]) done for j := n-2 down to 0, do minToken[m-1, j] := maximum of 1 and (minToken[m-1, j+1]-matrix[m-1, j]) done for i := m-2 down to 0, do for j := n-2 down to 0, do rem := minimum of minToken[i+1, j] and minToken[i, j+1] minPoint[i, j] := maximum of 1 and (rem – matrix[i,j]) done done return minToken[0, 0] End
示例
#include<iostream>
#include<cmath>
#define ROW 3
#define COL 3
using namespace std;
int tokens[ROW][COL] = {
{-2,-3,3},
{-5,-10,1},
{10,30,-5}
};
int max(int a, int b) {
return (a>b)?a:b;
}
int minInitPoints() {
int minToken[ROW][COL];
int m = ROW, n = COL;
minToken[m-1][n-1] = tokens[m-1][n-1] > 0? 1: abs(tokens[m-1][n-1]) + 1;
for (int i = m-2; i >= 0; i--) //from last row to first row, fill points
minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);
for (int j = n-2; j >= 0; j--) //fill last column to first column, fill points
minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);
for (int i=m-2; i>=0; i--) {
for (int j=n-2; j>=0; j--) {
int remPoint = min(minToken[i+1][j], minToken[i][j+1]); //calculate remaining points
minToken[i][j] = max(remPoint - tokens[i][j], 1);
}
}
return minToken[0][0];
}
int main() {
cout << "Minimum Points Required: " << minInitPoints();
}輸出
Minimum Points Required: 7
更新於： 2020年6月17日
847 次檢視
廣告