Given a point on x axis, (N,0), you are standing at origin and you can only move on x-axis. Lets say you are at (x,0), at each step you can either move one step forward ie (x+1,0) or one step backwards (x-1,0) or make a jump to double your current position (2*x,0). One step movement costs you A while a jump costs you B. If your initial position is (0,0) , find the minimum cost to reach (N,0) .
Example 1:
Input: N = 7, A = 1, B = 100
Output: 7
Explaination: Move forward to (N, 0) one 
unit at each step.
Example 2:
Input: N = 8, A = 2, B = 4
Output: 12
Explaination: The optimal movement is to 
1, 2, 3, 4, 8.
Your Task:
You do not need to read input or print anything. Your task is to complete the function optimalWalk() which takes N, A and B as input parameters and returns the minimum cost to go to (N, 0) from (0, 0).
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A, B ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def optimalWalk(self, N, A, B):
        # code here

Solutions:
class Solution:

	def optimalWalk(self, n, a, b):
		dp = [0] * (n + 1)
		dp[0] = 0
		dp[1] = a
		for i in range(2, n + 1):
			dp[i] = min(dp[i - 1] + a, dp[(i + 1) // 2] + b + i % 2 * a)
		return dp[n]


class Solution:

	def solve(self, n, a, b, dp):
		if n == 1:
			return a

	def optimalWalk(self, N, A, B):
		dp = [-1] * (N + 1)
		dp[0] = 0
		dp[1] = A
		for i in range(2, N + 1):
			d = min(A + dp[i - 1], A * (i % 2) + B + dp[(i + 1) // 2])
			dp[i] = d
		return dp[N]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def optimalWalk(self, N, A, B):
		dp = [0, A]
		for i in range(2, N + 1):
			d = min(A + dp[i - 1], A * (i % 2) + B + dp[(i + 1) // 2])
			dp.append(d)
		return dp[N]


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def optimalWalk(self, N, A, B):
		dp = [0] * (N + 1)
		dp[1] = A
		for i in range(2, N + 1):
			if i % 2 == 0:
				dp[i] = min(A + dp[i - 1], B + dp[i // 2])
			else:
				dp[i] = min(A + dp[i - 1], B + A + dp[(i + 1) // 2])
		return dp[-1]


class Solution:

	def optimalWalk(self, N, A, B):
		dp = [0 for i in range(N + 1)]
		dp[1] = A
		for i in range(2, N + 1):
			dp[i] = min(A + dp[i - 1], dp[(i + 1) // 2] + B + i % 2 * A)
		return dp[N]


class Solution:

	def optimalWalk(self, N, a, b):
		arr = [0] * (N + 1)
		arr[1] = a
		for i in range(2, N + 1):
			if i % 2 == 0:
				arr[i] = min(arr[i - 1] + a, arr[int(i / 2)] + b)
			else:
				arr[i] = min(arr[i - 1] + a, arr[int((i + 1) / 2)] + b + a)
		return arr[N]


class Solution:

	def optimalWalk(self, N, A, B):
		dp = [float('inf') for i in range(N + 1)]
		dp[0] = 0
		dp[1] = A
		for i in range(2, N + 1):
			dp[i] = min(dp[i - 1] + A, dp[(i + 1) // 2] + B + i % 2 * A)
		return dp[N]
		for i in range(1, N + 1):
			if i == N:
				dp[i] = min(dp[i - 1] + A, dp[i])
			else:
				dp[i] = min(dp[i - 1] + A, dp[i + 1] + A, dp[i])
				if 2 * i <= N:
					dp[2 * i] = min(dp[i] + B, dp[2 * i])
		return dp[N]


class Solution:

	def optimalWalk(self, n, A, B):
		f = [None for _ in range(n + 1)]
		f[0] = 0
		f[1] = A
		for i in range(2, n + 1):
			f[i] = min(A + f[i - 1], f[int((i + 1) / 2)] + B + i % 2 * A)
		return f[n]