Updating a dictionary of trajectories after a step has been made
Basic Review

You should import print_function from __future__. So you can use print like you can in Python 3.

Your variable names are poor.

j should be _.
What do j, k and d mean?
Why not just type out parts rather than use pts?


The way you're generating key value pairs in not amazing. If you make a function to build 20 keys then it would be much easier to understand. This is as things are split into two core aspects.

Building key
Building the dictionary


You should really use some functions.

You should really follow PEP 8. Your code is really hard to read because it looks like a block of characters, rather than a Python program.


Functional changes



A trajectory is defined as a list of numbers separated by _.

You should make it a tuple of numbers, (3, 7, 2, 5).



I also save the trajectories in separated dictionaries if they have different numbers of steps.

I see no reason to do this.

You may benefit from using a trie instead.
Since you're just printing the new dictionaries it doesn't make much sense.
However it looks exactly like what you want datatype wise.
I have included a build and an as_dict method to make understanding how it works a little simpler. You can easily remove the need for build by using it to build the trie directly from generate_keys.


from __future__ import print_function
import random


def generate_keys(amount, choices):
    for _ in range(amount):
        yield tuple(
            random.choice(choices[i])
            for i in range(random.randint(1, len(choices)))
        )


class Trie(dict):
    value = DEFAULT = object()

    @classmethod
    def build(cls, mapping):
        trie = cls()
        for keys, value in mapping.items():
            node = trie
            for key in keys:
                node = node.setdefault(key, cls())
            node.value = value
        return trie

    def _as_dict(self, path):
        for key, value in self.items():
            keys = path + (key,)
            if value.value is not self.DEFAULT:
                yield keys, value.value
            for item in value._as_dict(keys):
                yield item

    def as_dict(self):
        return dict(self._as_dict(()))


paths = {}
for key in generate_keys(20, [range(3), range(4), range(5)]):
    paths[key] = random.randrange(10)

trie = Trie.build(paths)
paths_new = trie[1].as_dict()

# Sort the output so it's easier to read
print('Initial dictionary =', dict(sorted(paths.items())))
print('Inital Trie =', trie)
print('Updated dictionaries =', dict(sorted(paths_new.items())))