最小傷害 題解，傷害題解
【問題描述】
把兒站在一個NxN的方陣中最左上角的格子裡。他可以從一個格子走到它右邊和下邊的格子裡。每一個格子都有一個傷害值。他想在受傷害最小的情況下走到方陣的最右下角。
給定N與N×N方陣中的傷害值，求出最小傷害。
【樣例輸入】
5
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
【樣例輸出】
2
【解題思路】
這道題與過河卒（NOIP2002)的思路一樣，且比過河卒更加容易（少了馬的控制），典型的遞推問題，用DP解決。
【動規方程】
f[i,j]:=min(f[i-1,j],f[i,j-1])+a[i,j](2<=i<=n，2<=j<=n);
【邊界條件】
f[1,1]:=a[1,1];f[1,i]:=f[1,i-1]+a[1,i](2<=i<=n);f[i,1]:=f[i-1,1]+a[i,1](2<=i<=n);
注意！最上邊和最左邊的兩排也要先賦值！
【代碼實現】
![]()
uses math;//這裡用了數學庫，就可以直接調用min函數，數學庫中有許多有用的函數，就不必自己手寫了。
var a,f:array[1..1000,1..1000] of longint;
i,j,n:longint;
begin
readln(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
//邊界賦值
f[1,1]:=a[1,1];
for i:=2 to n do
begin
f[1,i]:=f[1,i-1]+a[1,i];
f[i,1]:=f[i-1,1]+a[i,1];
end;
//動態規劃
for i:=2 to n do
for j:=2 to n do
f[i,j]:=min(f[i-1,j],f[i,j-1])+a[i,j];
writeln(f[n,n]);
end.
最小傷害
