Task 1: Minimum Sum Path
Find a path from top-left to bottom-right of an M x N grid which minimizes the sum of numbers along its path.
Example Output
Grid:
[1, 3, 1]
[1, 5, 1]
[4, 2, 1]
Minimum sum: 7
Logic
Use dynamic programming where table[i][j] = matrix[i][j] + min(table[i-1][j], table[i][j-1]).
Perl Solution
ch-1.pl
sub min_sum_path {
my ($matrix) = @_;
my $rows = @$matrix; my $cols = @{$matrix->[0]};
for my $i (0 .. $rows-1) {
for my $j (0 .. $cols-1) {
next if $i == 0 && $j == 0;
my $top = $i > 0 ? $matrix->[$i-1][$j] : 1e9;
my $left = $j > 0 ? $matrix->[$i][$j-1] : 1e9;
$matrix->[$i][$j] += $top < $left ? $top : $left;
}
}
return $matrix->[-1][-1];
}
Python Solution
ch-1.py
def min_sum_path(matrix: List[List[int]]) -> int:
rows, cols = len(matrix), len(matrix[0])
for i in range(rows):
for j in range(cols):
if i == 0 and j == 0: continue
top = matrix[i-1][j] if i > 0 else float('inf')
left = matrix[i][j-1] if j > 0 else float('inf')
matrix[i][j] += min(top, left)
return matrix[-1][-1]
Task 2: Word Break
Determine if string S can be segmented into a space-separated sequence of dictionary words.
Example Output
S = 'perlweeklychallenge', W = ['weekly', 'challenge', 'perl']
Result: ['perl', 'weekly', 'challenge']
Logic
Recursive backtracking / DP matching dictionary prefixes against the remaining substring.
Perl Solution
ch-2.pl
sub helper {
my ($s, $W, $words) = @_;
return $words if length($s) == 0;
for my $word (@$W) {
if ($s =~ /^\Q$word\E/) {
my $res = helper(substr($s, length($word)), $W, [@$words, $word]);
return $res if $res;
}
}
return undef;
}
Python Solution
ch-2.py
def word_break(s: str, words: List[str]) -> List[str]:
def helper(sub_s, path):
if not sub_s: return path
for w in words:
if sub_s.startswith(w):
res = helper(sub_s[len(w):], path + [w])
if res: return res
return None
return helper(s, [])