題意

給定M*N的矩陣，其中的每個元素都是-10到10之間的整數(shù)。你的任務(wù)是從左上角（1，1）走到右下角（M，N），每一步只能向右或向下，并且不能走出矩陣的范圍。你所經(jīng)過的方格里面的數(shù)字都必須被選取，請找出一條最合適的道路，使得在路上被選取的數(shù)字之和是盡可能小的正整數(shù)。

分析

設(shè)f[i,j,k]為到i、j,數(shù)k存不存在?
if a[i-1,j,k]=true then f[i,j,k+a[i,j]]:=true?
if a[i,j-1,k]=true then f[i,j,k+a[i,j]]:=true

var
m,n,i,j,k,bz:longint;
a:array[0..11,0..11]of longint;
f:array[0..11,0..11,-2000..2000]of boolean;
begin
? ? readln(n,m);
? ? for i:=1 to n do
? ? begin
? ? ? ? for j:=1 to m do
? ? ? ? read(a[i,j]);
? ? ? ? readln;
? ? end;
? ? fillchar(f,sizeof(f),false);
? ? f[1,1,a[1,1]]:=true;


? ? for i:=2 to m do
? ? for k:=-1000 to 1000 do
? ? if f[1,i-1,k] then f[1,i,k+a[1,i]]:=true;


? ? for i:=2 to n do
? ? for k:=-1000 to 1000 do
? ? if f[i-1,1,k] then f[i,1,k+a[i,1]]:=true;


? ? for i:=2 to n do
? ? begin
? ? ? ? for j:=2 to m do
? ? ? ? begin
? ? ? ? ? ? for k:=-1000 to 1000 do
? ? ? ? ? ? if f[i,j-1,k] then f[i,j,k+a[i,j]]:=true;


? ? ? ? ? ? for k:=-1000 to 1000 do
? ? ? ? ? ? if f[i-1,j,k] then f[i,j,k+a[i,j]]:=true;
? ? ? ? end;
? ? end;
? ? i:=1;
? ? while (f[n,m,i]=false)and(i<=1000) do inc(i);
? ? if i>1000 then write(-1) else write(i);
end.

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500169.html

總結(jié)

以上是生活随笔為你收集整理的取数字问题:动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。