[Python] Write a program that uses dynamic programming to solve the following problem. Find...

I've been trying to solve this question. Need it done in python. Every time I try I somehow get to the wrong answers and I think I may be trying to hard to figure it out. Someone please help me figure out what is wrong. Here's a pic of the question:

Pic of Question

This is the template I'm given to fill out:


import math

# Point class
class Point:
def __init__(self):
self.x = 0
self.y = 0


# Main program
# Read in x and y for Point P
p = Point()
p.x = int(input())
p.y = int(input())

# Read in num of steps to be taken in X and Y directions

# Read in num of steps to be taken (backwards) every 3 steps

# Write dynamic programming algorithm

# Output

I've tried so many things and eventually tried to do this while making it end after 30 iterations, but only updating all the numbers with the smallest distance from point P. Not sure why it's wrong but this is my code:


import math

# Point class
class Point:
def __init__(self):
self.x = 0
self.y = 0


# Main program
# Read in x and y for Point P
p = Point()
p.x = int(input())
p.y = int(input())

# Read in num of steps to be taken in X and Y directions
num_x = int(input())
num_y = int(input())
# Read in num of steps to be taken (backwards) every 3 steps
num_back = int(input())
# Write dynamic programming algorithm
curr = Point()
previous = Point()

curr.x += num_x
curr.y += num_y
d1 = math.sqrt((p.x - previous.x)**2 + (p.y - previous.y)**2)
d2 = math.sqrt((p.x - curr.x)**2 + (p.y - curr.y)**2)
count = 1
num_steps = 0
final = Point()
while True:
if count == 30:
break
else:
count += 1
previous.x = curr.x
previous.y = curr.y
if count % 3 == 0:
curr.x -= num_back
curr.y -= num_back
else:
curr.x += num_x
curr.y += num_y
if d2 < d1:
d1 = d2
num_steps = count
final.x = curr.x
final.y = curr.y
d2 = math.sqrt((p.x - curr.x)**2 + (p.y - curr.y)**2)
# Output
print(f'Point P: ({p.x},{p.y})')
print(f"Arrival point: ({final.x},{final.y})")
print(f'Distance between P and arrival: {d1: 6f}')
print(f'Number of iterations: {num_steps}')

Continue reading...